Aarhus University Seal

Improved Range Searching Lower Bounds

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Table of Contents


In this paper we present a number of improved lower bounds for range searching in the pointer machine and the group model. In the pointer machine, we prove lower bounds for the approximate simplex range reporting problem. In approximate simplex range reporting, points that lie within a distance of ε ⋅ Diam(s) from the border of a query simplex s, are free to be included or excluded from the output, where ε ≥ 0 is an input parameter to the range searching problem. We prove our lower bounds by constructing a hard input set and query set, and then invoking Chazelle and Rosenberg's [CGTA'96] general theorem on the complexity of navigation in the pointer machine. For the group model, we show that input sets and query sets that are hard for range reporting in the pointer machine (i.e. by Chazelle and Rosenberg's theorem), are also hard for dynamic range searching in the group model. This theorem allows us to reuse decades of research on range reporting lower bounds to immediately obtain a range of new group model lower bounds. Amongst others, this includes an improved lower bound for the fundamental problem of dynamic d-dimensional orthogonal range searching, stating that tqtu = Ω((lg n/lg lg n)d-1). Here tq denotes the query time and tu the update time of the data structure. This is an improvement of a lg1-δn factor over the recent lower bound of Larsen [FOCS'11], where δ>0 is a small constant depending on the dimension.
Original languageEnglish
Title of host publicationProceedings of the 2012 symposuim on Computational Geometry : Chapel Hill, NC, USA — June 17 - 20, 2012
Number of pages8
PublisherAssociation for Computing Machinery
Publication year2012
ISBN (print)978-1-4503-1299-8
Publication statusPublished - 2012
Event28th ACM Symposium on Computational Geometry - The University of North Carolina, Chapel Hill, NC, United States
Duration: 17 Jun 201220 Jun 2012


Conference28th ACM Symposium on Computational Geometry
LocationThe University of North Carolina
LandUnited States
ByChapel Hill, NC

See relations at Aarhus University Citationformats

ID: 51725418