PaperlayerView exact revision on arXiv

Source-linked AI summary

Orthogonal Range Searching on the RAM, Revisited

Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu

arXiv:1103.5510v1cs.CGcs.DS

TL;DR

This paper studies orthogonal range searching in the standard word RAM model for rank-space points, including online and offline problems. It develops new data structures and randomized algorithms, obtaining improved bounds for 2-d emptiness, higher-dimensional reporting, and offline 4-d dominance problems.

  • Problem

    Orthogonal range searching lacks equally strong bounds across online and offline problems in the standard word RAM model, whose performance is studied here for internal-memory computation.

  • Method

    The paper combines range trees, randomized 3-d shallow cuttings, collective 3-d transformations of point-location subproblems, and RAM-based data structures.

  • Results

    The paper obtains improved bounds including O(n lg lg n) space and O(lg lg n) query time for 2-d range emptiness, and expected O(n lg n + k) time for offline 4-d dominance reporting.

  • Takeaways & Limitations

    These results give the best RAM upper bounds known in the paper's scope and improve bounds for orthogonal range reporting in constant dimensions above 3.

  • Takeaways & Limitations

    The data-structure results assume rank-space coordinates; general coordinates require an additional predecessor-search cost, and direct 4-d shallow cuttings are inadvisable because their staircase polyhedra can have quadratically many vertices.

Abstract

from arXiv · show

We present several 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 for points in rank space: ** We present two data structures for 2-d orthogonal range emptiness. The first achieves O(n lglg n) space and O(lglg n) query time. This improves the previous results by Alstrup, Brodal, and Rauhe(FOCS'00), with O(n lg^eps n) space and O(lglg n) query time, or with O(nlglg n) space and O(lg^2 lg n) query time. Our second data structure uses O(n) space and answers queries in O(lg^eps n) time. The best previous O(n)-space data structure, due to Nekrich (WADS'07), answers queries in O(lg n/lglg n) time. ** For 3-d orthogonal range reporting, we obtain space O(n lg^{1+eps} n) and query time O(lglg n + k), for any constant eps>0. This improves previous results by Afshani (ESA'08), Karpinski and Nekrich (COCOON'09), and Chan (SODA'11), with O(n lg^3 n) space and O(lglg n + k) query time, or with O(n lg^{1+eps} n) space and O(lg^2 lg n + k) query time. This implies improved bounds for orthogonal range reporting in all constant dimensions above 3. ** We give a randomized algorithm for 4-d offline dominance range reporting/emptiness with running time O(n lg n + k). This resolves two open problems from Preparata and Shamos' seminal book: **** given n axis-aligned rectangles in the plane, we can report all k enclosure pairs in O(n lg n + k) expected time. The best known result was an O([n lg n + k] lglg n) algorithm from SoCG'95 by Gupta, Janardan, Smid, and Dasgupta. **** given n points in 4-d, we can find all maximal points in O(n lg n) expected time. The best previous result was an O(n lg n lglg n) algorithm due to Gabow, Bentley, and Tarjan (STOC'84). This implies record time bounds for the maxima problem in all constant dimensions above 4.

1 Introduction

The paper develops improved word-RAM bounds for orthogonal range searching in rank space, covering online emptiness and reporting as well as offline dominance problems. These results also improve bounds for higher-dimensional reporting and maxima.

  • Scope: The paper studies orthogonal range searching in the standard word RAM model for rank-space point sets.The problems include counting, aggregation, emptiness, and reporting in axis-aligned ranges.
  • Online range searching: O(n lg lg n) space yields optimal O(lg lg n) query time for 2-d range emptiness.This simultaneously improves both prior Alstrup–Brodal–Rauhe trade-offs.
  • Online range searching: O(n lg^{1+ε} n) space and O(lg lg n + k) query time are achieved for 3-d orthogonal range reporting.The result improves previous bounds and implies improved bounds in all constant dimensions above 3.
  • Additional result: The paper also obtains O(n lg^ε n) space and O(lg lg n) query time for 2-d range minimum queries.This result follows by modifying the 3-d range reporting method.
  • Offline range searching: O(n lg n + k) expected time solves offline 4-d dominance reporting, improving the previous O((n lg n + k) lg lg n) bound.The algorithm is randomized and k denotes total output size.
  • Offline range searching: The 4-d offline result gives O(n lg n) expected time for maxima and improves maxima bounds in all constant dimensions above 4.It is the first improvement over the cited worst-case bound in two and a half decades.

2 Range Reporting in 2-d

The 2-d reporting structure is reduced to a ball-inheritance problem on a binary tree. Skip-list-like pointer layouts then produce explicit space–query trade-offs, which transfer to reporting and emptiness.

  • Range-reporting bounds: At the trade-off extremes, reporting uses O(n) space with O(lg^ε n) query time or O(n lg^ε n) space with O(lg lg n + k) query time.Setting k = 0 transfers the trade-offs to range emptiness.
  • Reduction: 2-d range reporting is reduced in linear space to the ball-inheritance problem, a pointer-chasing problem on a perfect binary tree.The abstract query asks which leaf an indexed ball eventually reaches from a given node.
  • Ball-inheritance trade-offs: For 2 ≤ B ≤ lg^ε n, ball inheritance supports O(nB lg lg n) space and O(lg_B lg n) query time.This is the fast-query, higher-space trade-off.
  • Ball-inheritance trade-offs: For 2 ≤ B ≤ lg^ε n, ball inheritance also supports O(n lg_B lg n) space and O(B lg lg n) query time.This is the low-space, slower-query trade-off.
  • Implementation: Constant-time rank structures encode ball transitions between tree levels, enabling pointer traversal and the reduction from ball inheritance to range reporting.The range-reporting query uses LCA computation, predecessor searches, RMQ, and ball inheritance.

3 Range Reporting in 3-d

The paper presents a recursive grid-based data structure for 3-d orthogonal range reporting, achieving near-linear-polylogarithmic space and O(lg lg U + k) query time. Bootstrapping and rank-space reduction yield the stated rank-space bounds and extensions to higher-dimensional reporting, emptiness, and range minimum queries.

  • The data structure: A grid with n/(Ct) rows and t columns supports recursive column structures, row structures, column reporting, and representative-point queries.Each nonempty grid cell contributes its lowest-z point to the representative set G.
  • The query algorithm: O(lg lg U + k) query time follows by combining the top row, boundary columns, interior representative set, and z-sorted grid-cell lists.The resulting recurrence is Q(n, k) = Q0(Ct, k′) + O(lg lg U + k − k′).
  • Bootstrapping and rank-space reduction: Bootstrapping ⌈1/ε⌉ times gives O(n lg U + n lg^{1+ε} n) bits of space, or O(n lg^ε n) words after packing.The query time remains O(lg lg U + k).
  • Higher dimensions and applications: O(n lg^{d−2+ε} n) space and O((lg n / lg lg n)^{d−3} lg lg n + k) query time follow for constant dimensions d ≥ 4.The same bounds hold for emptiness when k is set to 0.
  • Higher dimensions and applications: O(n lg^ε n) space and O(lg lg U) query time are obtained for 2-d range minimum queries, with a related 2-d reporting result of O(n lg^ε n) space and O(lg lg U + k) time.The range-minimum reduction uses 3-d 5-sided emptiness and 2-d dominance range-minimum structures.

4 Offline Range Reporting

The paper develops randomized and RAM-oriented tools for offline dominance reporting, culminating in expected O(n lg n + k) time in 4-d and extensions to higher dimensions and related problems.

  • 4.1 Preliminaries: Randomized 3-d shallow cuttings use a sample R, staircase polyhedron P(R), and vertical decomposition VD(R) with O(|R|) size.The decomposition supports conflict-list processing and point-location-based recursion.
  • 4.2 Offline 3-d Dominance Reporting: O(n lg lg n + k) expected time solves offline 3-d dominance reporting, improving to O(n + k) when n ≤2O(√w) and coordinates are pre-sorted.The algorithm samples input points and recursively handles bad queries.
  • 4.3 Offline 4-d Dominance Reporting: A range tree reduces the 4-d problem to 3-d subproblems, but additional ideas are needed to improve the naive O(n lg n lg lg n + k) bound.The final construction solves subproblems across range-tree levels while controlling point-location and output costs.
  • 4.3 Offline 4-d Dominance Reporting: O(n lg n + k) expected time solves offline 4-d dominance reporting on n input points and n query points.Here, k is the total output size.
  • 4.4 Consequences: O(n lg^{d−3} n + k) expected time extends offline dominance reporting to every constant dimension d ≥4.With k set to 0, the same bounds apply to offline dominance emptiness.
  • 4.4 Consequences: O(n lg^{d−3} n) expected time solves maxima, bichromatic L∞-closest pair, and L∞-minimum spanning tree problems in constant dimensions d ≥4.These consequences follow from the offline dominance results.

A.1 Succinct Rank Queries (Proof of Lemma 2.3)

The proof stores periodic checkpoints and uses a two-level checkpoint scheme when the alphabet is small, enabling constant-time rank queries within the stated space bound.

  • A.1 Succinct Rank Queries: O(lg(Σ lg n)) bits per element fit the space bound when checkpoints are stored every Σ lg n positions.Each checkpoint records counts for the relevant element kinds before its position.
  • A.1 Succinct Rank Queries: Constant-time rank queries add the counter stored with A[i] to the appropriate counter from the last checkpoint.This applies to the primary checkpoint structure.
  • A.1 Succinct Rank Queries: A two-level scheme adds minor checkpoints every Σ lg lg n positions when the alphabet is smaller.Minor checkpoints bridge the last major checkpoint and the query position.
  • A.1 Succinct Rank Queries: O(√lg n · lg^2 lg n) bits suffice for array entries between minor checkpoints, allowing plain storage and constant-time table-based rank queries.The table is precomputed with space n^o(1).

A.2 Offline 2-d Orthogonal Point Location for Few Points (Proof of Lemma 4.1)

The few-point orthogonal point-location algorithm uses bit packing and a trie-based reduction to disjoint-interval stabbing, achieving linear time under a small-input condition.

  • A.2 Offline 2-d Orthogonal Point Location for Few Points: The method reduces point location to 1-d disjoint-interval stabbing problems over trie nodes.Each point is assigned to the interval containing it, if one exists.
  • A.2 Offline 2-d Orthogonal Point Location for Few Points: Packed sorted interval lists are constructed across O(lg n) trie levels using table lookups and external-memory radix sorting.The construction time is O((n lg^2 n)/w).
  • A.2 Offline 2-d Orthogonal Point Location for Few Points: O(n) total time follows because packed scans cost O((n lg^2 n)/w + n) when n ≤2O(√w), with total output size O(n).Queries and intervals are scanned together using table lookups.

A.3 An Alternative Algorithm for a Special Case of 4-d Offline Dominance Emptiness

The section gives an alternative algorithm for a special 4-d offline dominance emptiness case by reducing dominance to halfspace range searching and using convex-polyhedron operations. A binary range tree combines 3-d subproblems in O(n lg n) time, while the approach does not extend to reporting or full offline emptiness.

  • Reduction to halfspace range searching: An exponentially spaced grid gives an explicit reduction from dominance range searching to halfspace range searching.The reduction applies first to the 3-d subproblem.
  • Convex-polyhedron formulation: The 3-d red/blue dominance answer is characterized by containment of the red convex hull P inside the intersection Q of complements of blue halfspaces.The condition is equivalent to P ∩ Q = P, enabling a convex-polyhedron intersection test.
  • Extension to 4-d: A binary range tree on the fourth coordinate produces 3-d subproblems of total size O(n lg n).Red convex hulls and blue halfspace structures are precomputed bottom-up using linear-time polyhedral operations.
  • Running time: O(n lg n) overall time solves the stated 4-d special case deterministically.The construction combines the range-tree decomposition with precomputed convex hulls and halfspace structures.
  • Limitation: The approach does not work for offline dominance reporting or the full offline dominance emptiness problem.The 3-d subproblem leaves non-maximal blue query points unresolved when their halfspaces do not lie on ∂Q.
Loading 1103.5510v1…