Title: On the complexity of range searching among curves,
Abstract: Modern tracking technology has made the collection of large numbers of
densely sampled trajectories of moving objects widely available. We consider a
fundamental problem encountered when analysing such data: Given $n$ polygonal
curves $S$ in $\mathbb{R}^d$, preprocess $S$ into a data structure that answers
queries with a query curve $q$ and radius $\rho$ for the curves of $S$ that
have \Frechet distance at most $\rho$ to $q$.
We initiate a comprehensive analysis of the space/query-time trade-off for
this data structuring problem. Our lower bounds imply that any data structure
in the pointer model model that achieves $Q(n) + O(k)$ query time, where $k$ is
the output size, has to use roughly $\Omega\left((n/Q(n))^2\right)$ space in
the worst case, even if queries are mere points (for the discrete \Frechet
distance) or line segments (for the continuous \Frechet distance). More
importantly, we show that more complex queries and input curves lead to
additional logarithmic factors in the lower bound. Roughly speaking, the number
of logarithmic factors added is linear in the number of edges added to the
query and input curve complexity. This means that the space/query time
trade-off worsens by an exponential factor of input and query complexity. This
behaviour addresses an open question in the range searching literature: whether
it is possible to avoid the additional logarithmic factors in the space and
query time of a multilevel partition tree. We answer this question negatively.
On the positive side, we show we can build data structures for the \Frechet
distance by using semialgebraic range searching. Our solution for the discrete
\Frechet distance is in line with the lower bound, as the number of levels in
the data structure is $O(t)$, where $t$ denotes the maximal number of vertices
of a curve. For the continuous \Frechet distance, the number of levels
increases to $O(t^2)$.