Orthogonal range searching on the RAM, revisited
From MaRDI portal
Publication:5404401
DOI10.1145/1998196.1998198zbMATH Open1283.68139arXiv1103.5510OpenAlexW2135639194MaRDI QIDQ5404401FDOQ5404401
Authors: Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu 
Publication date: 24 March 2014
Published in: Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1103.5510
Recommendations
- Dynamic orthogonal range searching on the RAM, revisited
- Cache-oblivious data structures for orthogonal range searching
- Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
- Orthogonal range searching in linear and almost-linear space
- Orthogonal Range Searching in Linear and Almost-Linear Space
- On the average performance of orthogonal range search in multidimensional data structures
- scientific article; zbMATH DE number 2086648
- Cache-oblivious planar orthogonal range searching and counting
- Space-Time Trade-Offs for Orthogonal Range Queries
- Compact and succinct data structures for multidimensional orthogonal range searching
Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cited In (85)
- Approximating Distance Measures for the Skyline
- Title not available (Why is that?)
- On reporting the \(L_1\) metric closest pair in a query rectangle
- A linear-space data structure for range-LCP queries in poly-logarithmic time
- Submatrix maximum queries in Monge matrices are equivalent to predecessor search
- On constant factors in comparison-based geometric algorithms and data structures
- Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries
- Orthogonal point location and rectangle stabbing queries in 3-d
- Adaptive data structures for 2D dominance colored range counting
- Finding a Maximum Clique in a Grounded 1-Bend String Graph
- Elastic-degenerate string matching with 1 error or mismatch
- Internal shortest absent word queries in constant time and linear space
- Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads
- Connectivity oracles for graphs subject to vertex failures
- A simple grammar-based index for finding approximately longest common substrings
- On approximate colored path counting
- Linear space adaptive data structures for planar range reporting
- Near-optimal search time in \(\delta \)-optimal space, and vice versa
- Two approaches to building time-windowed geometric data structures
- Independent range sampling, revisited
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Dictionary matching with a few gaps
- Fast local searches and updates in bounded universes
- Succinct indices for path minimum, with applications
- Dynamic geometric data structures via shallow cuttings
- Dictionary matching with uneven gaps
- Orthogonal range searching in linear and almost-linear space
- Kinetic \(k\)-semi-Yao graph and its applications
- Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model
- Flexible indexing of repetitive collections
- On hardness of several string indexing problems
- Document retrieval with one wildcard
- Optimal deterministic shallow cuttings for 3-d dominance ranges
- Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in \(\mathbb R^3\)
- Time-optimal top-\(k\) document retrieval
- Fast construction of wavelet trees
- Less space: indexing for queries with wildcards
- Skyline Computation with Noisy Comparisons
- Extracting powers and periods in a word from its runs structure
- Compressed indexes for text with wildcards
- Space-efficient data-analysis queries on grids
- Substring range reporting
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- The heaviest induced ancestors problem revisited
- Top-\(k\) document retrieval in optimal time and linear space
- Range LCP
- Time windowed data structures for graphs
- An LMS-based grammar self-index with local consistency properties
- The heaviest induced ancestors problem: better data structures and applications
- Dynamic and internal longest common substring
- Data structures for categorical path counting queries
- Elastic-degenerate string matching with 1 error
- Title not available (Why is that?)
- The range 1 query (R1Q) problem
- Compact binary relation representations with rich functionality
- Towards an optimal method for dynamic planar point location
- Composite repetition-aware data structures
- Fast string dictionary lookup with one error
- Two-dimensional range successor in optimal time and almost linear space
- Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
- Grammar-compressed indexes with logarithmic search time
- Ranked document selection
- Orthogonal range searching for text indexing
- Succinct and Implicit Data Structures for Computational Geometry
- Deterministic rectangle enclosure and offline dominance reporting on the RAM
- Sorted range reporting
- On Geometric Set Cover for Orthants
- A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
- Position-restricted substring searching over small alphabets
- On Dominance Reporting in 3D
- Group nearest-neighbor queries in the \(L_1\) plane
- Compressed text indexing with wildcards
- Generalized substring compression
- Wavelet trees for all
- Time-space trade-offs for Lempel-Ziv compressed indexing
- Fast relative Lempel-Ziv self-index for similar sequences
- On position restricted substring searching in succinct space
- Universal compressed text indexing
- Dictionary matching with a bounded gap in pattern or in text
- A self-index on block trees
- Path queries on functions
- Cache-oblivious data structures for orthogonal range searching
- The fine-grained complexity of multi-dimensional ordering properties
- Sequential dependency computation via geometric data structures
- Entropy-bounded representation of point grids
This page was built for publication: Orthogonal range searching on the RAM, revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404401)
