Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Orthogonal Range Reporting: Query Lower Bounds, Optimal Structures in 3-d, and Higher Dimensional Improvements

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Department of Computer Science
Orthogonal range reporting is the problem of storing a set of n points in d-dimensional space, such that the k points in an axis-orthogonal query box can be reported efficiently. While the 2-d version of the problem was completely characterized in the pointer machine model more than two decades ago, this is not the case in higher dimensions.

In this paper we provide a space optimal pointer machine data structure for 3-d orthogonal range reporting that answers queries in O(log n + k) time. Thus we settle the complexity of the problem in 3-d. We use this result to obtain improved structures in higher dimensions, namely structures with a log n/ log log n factor increase in space and query time per dimension. Thus for d e 3 we obtain a structure that both uses optimal O(n(log n/ log log n)d--1) space and answers queries in the best known query bound O(log n(log n/ log log n)d--3 + k).

Furthermore, we show that any data structure for the d-dimensional orthogonal range reporting problem in the pointer machine model of computation that uses S(n) space must spend Ω((log n/ log(S(n)/n))⌊d/2⌋--1) time to answer queries. Thus, if S(n)/n is poly-logarithmic, then the query time is at least Ω((log n/ log log n)⌊d/2⌋--1). This is the first known non-trivial higher dimensional orthogonal range reporting query lower bound and it has two important implications. First, it shows that the query bound increases with dimension. Second, in combination with our upper bounds it shows that the optimal query bound increases from Θ(log n + k) to Ω((log n/ log log n)2 + k) somewhere between three and six dimensions.

Finally, we show that our techniques also lead to improved structures for point location in rectilinear subdivisions, that is, the problem of storing a set of n disjoint d-dimensional axis-orthogonal rectangles, such that the rectangle containing a query point q can be found efficiently.
Original languageEnglish
JournalAnnual A C M Symposium on Computational Geometry. Proceedings
Pages (from-to)240-246
Number of pages7
ISSN1055-6257
DOIs
Publication statusPublished - 2010
Event25th Annual ACM Symposium on Computational Geometry - Århus, Denmark
Duration: 8 Jun 200910 Jun 2009

Conference

Conference25th Annual ACM Symposium on Computational Geometry
CountryDenmark
CityÅrhus
Period08/06/200910/06/2009

Bibliographical note

Title of the vol.: Proceedings of the 2010 annual symposium on Computational geometry.SoCG '10 / Program Chairs: David Kirkpatrick, Joseph Mitchell
ISBN: 978-1-4503-0016-2

See relations at Aarhus University Citationformats

ID: 34485428