Orthogonal range searching on the RAM, revisited

Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu

TL;DR

This paper revisits fundamental problems in orthogonal range searching, achieving new record-breaking time and space complexities for 2D range emptiness, 3D range reporting, and 4D offline dominance reporting. The work significantly advances the state-of-the-art in computational geometry, resolving long-standing open problems.

What Problem Does This Paper Address?

Computational geometry has long been fascinated by "orthogonal range searching" problems. Imagine you have a set of points in a multi-dimensional space, and you want to efficiently answer queries about points within a specific rectangular region (or "box"). Common queries include:

  • Emptiness: Is there any point in this box?
  • Reporting: List all points in this box.
  • Minimum: Find the point with the minimum "value" (e.g., smallest y-coordinate) within this box.
  • Dominance: Given a set of points, find points that are "maximal" (not dominated by any other point).

These problems are crucial for many applications, from database queries to computer graphics. While decades of research have yielded impressive results, many questions remained open, particularly concerning the trade-offs between the space required for data structures and the time taken to answer queries. This paper tackles these challenges in the standard "word RAM" model, aiming to push the boundaries of efficiency for these core geometric problems.

Methods

The authors introduce several novel techniques and combine existing ones in new ways:

  • Ball Inheritance Problem: A new abstract problem is introduced to model pointer-chasing in a tree structure. This is then used as a building block for efficient 2D range reporting.
  • Succinct Data Structures: Leveraging techniques for succinct data structures (like those for rank queries) is key to achieving space efficiency.
  • Randomized Shallow Cuttings: For offline problems (where all queries are known in advance), the paper employs a randomized version of shallow cuttings. This technique decomposes the space and allows for efficient processing of subproblems.
  • Bit-Packing and Word RAM Techniques: The authors utilize bit-packing and other word RAM specific optimizations to achieve speedups, especially in the offline setting.
  • Recursive Structure and Divide-and-Conquer: Many of the algorithms are built upon recursive structures, breaking down higher-dimensional problems into lower-dimensional ones.
  • Bootstrapping: For some problems, a bootstrapping technique is used to iteratively improve the performance of a data structure.

What's particularly noteworthy is the development of new techniques for 2D range reporting that are not based on prior grid-based approaches, and a clever combination of bit-packing and geometric tools for the offline 4D problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and data structures, analyzing their performance on abstract sets of points and geometric objects rather than specific datasets.

Key Insights and Ideas

  • The Power of Abstraction: Introducing the "ball inheritance" problem provides a clean, abstract model that simplifies the design of complex geometric data structures.
  • Bridging Online and Offline: The paper demonstrates how techniques developed for online problems (like range reporting) can be adapted and extended to solve offline problems more efficiently, particularly using randomized shallow cuttings.
  • Resolving Decades-Old Questions: The paper provides the first O(n log n + k) algorithm for the 2D rectangle enclosure problem, a problem that had remained open for over 30 years. Similarly, it achieves the first O(n log n) algorithm for the 4D maxima problem.
  • "Adding Sides" is Efficient: The work shows that extending 3D range reporting to higher dimensions or to more general query types (like 5-sided or 6-sided boxes) can be done with surprisingly small increases in complexity.

Key Results

The paper presents several significant improvements over previous state-of-the-art results:

  • 2D Orthogonal Range Emptiness:
    • O(n lg lg n) space and O(lg lg n) query time (improving on previous O(n lgε n) space / O(lg lg n) time or O(n lg lg n) space / O(lg² lg n) time).
  • O(n) space and O(lg n) query time (improving on previous O(n) space / O(lg n / lg lg n) time).
  • 3D Orthogonal Range Reporting:
    • O(n lg¹⁺ε n) space and O(lg lg n + k) query time (improving on previous O(n lg³ n) space / O(lg lg n + k) time or O(n lg¹⁺ε n) space / O(lg² lg n + k) time).
  • 2D Orthogonal Range Minimum Queries:
    • O(n lgε n) space and O(lg lg n) query time.
  • 4D Offline Dominance Reporting/Emptiness:
    • Randomized O(n lg n + k) expected time. This resolves two open problems:
  • Reporting enclosure pairs of rectangles in 2D in O(n lg n + k) expected time.
  • Finding maximal points in 4D in O(n lg n) expected time.
  • Higher Dimensions: The results extend to d-dimensional problems, providing improved bounds for d ≥ 4.

Limitations and Future Work

  • Randomization: The most significant result for offline 4D dominance reporting is randomized. While the analysis provides strong probabilistic guarantees, a deterministic version would be ideal.
  • Rank Space Assumption: For some results, the analysis assumes points are in "rank space" (coordinates are integers from 0 to n-1). While the paper explains how to reduce general coordinates to this case, it adds a small overhead.
  • Open Problems: The paper mentions that the 2D range reporting problem with O(n) space and O(lg n + k) query time is still an open problem.
  • Future Work: The authors suggest that their techniques for 2D range reporting are novel and could lead to further advancements. The paper also hints at potential applications in other areas like bichromatic L∞-closest pair and L∞-minimum spanning tree problems.

Summary updated

Abstract

We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: We present two data structures for 2-d orthogonal range emptiness. The first achieves O(n lg lg n) space and O(lg lg n) query time, assuming that the n given points are in rank space. This improves the previous results by Alstrup, Brodal, and Rauhe (FOCS'00), with O(n lgε n) space and O(lg lg n) query time, or with O(n lg lg n) space and O(lg2lg n) query time. Our second data structure uses O(n) space and answers queries in O(lgε n) time. The best previous O(n)-space data structure, due to Nekrich (WADS'07), answers queries in O(lg n/lg lg n) time. We give a data structure for 3-d orthogonal range reporting with O(n lg1+ε n) space and O(lg lg n + k) query time for points in rank space, for any constant ε>0. This improves the previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(n lg3 n) space and O(lg lg n + k) query time, or with O(n lg1+εn) space and O(lg2lg n + k) query time. Consequently, we obtain improved upper bounds for orthogonal range reporting in all constant dimensions above 3. Our approach also leads to a new data structure for 2D orthogonal range minimum queries with O(n lgε n) space and O(lg lg n) query time for points in rank space. We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time O(n log n) plus the output size. This resolves two open problems (both appeared in Preparata and Shamos' seminal book): given a set of n axis-aligned rectangles in the plane, we can report all k enclosure pairs (i.e., pairs (r1,r2) where rectangle r1 completely encloses rectangle r2) in O(n lg n + k) expected time; given a set of n points in 4-d, we can find all maximal points (points not dominated by any other points) in O(n lg n) expected time. The most recent previous development on (a) was reported back in SoCG'95 by Gupta, Janardan, Smid, and Dasgupta, whose main result was an O([n lg n + k] lg lg n) algorithm. The best previous result on (b) was an O(n lg n lg lg n) algorithm due to Gabow, Bentley, and Tarjan---from STOC'84! As a consequence, we also obtain the current-record time bound for the maxima problem in all constant dimensions above~4.
BibTeX
@inproceedings{chan2011orthogonal,
  author = {Timothy M. Chan and Kasper Green Larsen and Mihai Patrascu},
  title = {{Orthogonal range searching on the RAM, revisited}},
  booktitle = {Symposium on Computational Geometry},
  year = {2011},
  url = {https://openreview.net/forum?id=Ui19HopCGdB},
}
Figure