On the complexity of range searching among curves

Peyman Afshani, Anne Driemel

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)


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 Rd, preprocess S into a data structure that answers queries with a query curve q and radius p for the curves of S that have Fréchet distance at most p 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 Ω (n=Q(n))2) space in the worst case, even if queries are mere points (for the discrete Fréchet distance) or line segments (for the continuous Fréchet 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 (see [1, 9]) in the range searching literature concerning multilevel partition trees which may be of independent interest, namely, 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 Fréchet distance by using semialgebraic range searching. The space/query-time trade-off of our data structure for the discrete Fréchet 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 Fréchet distance, the number of levels increases to O(t2).

Original languageEnglish
Title of host publication29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
PublisherAssociation for Computing Machinery, Inc
Number of pages20
ISBN (Electronic)9781611975031
Publication statusPublished - 1 Jan 2018
Event29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) - Astor Crowne Plaza, New Orleans, United States
Duration: 7 Jan 201810 Jan 2018
Conference number: 29


Conference29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
Abbreviated titleSODA 2018
CountryUnited States
CityNew Orleans
Internet address

Fingerprint Dive into the research topics of 'On the complexity of range searching among curves'. Together they form a unique fingerprint.

  • Cite this

    Afshani, P., & Driemel, A. (2018). On the complexity of range searching among curves. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (pp. 898-917). Association for Computing Machinery, Inc. https://doi.org/10.1137/1.9781611975031.58