Orthogonal range searching on the RAM, revisited
From MaRDI portal
(Redirected from Publication:5404401)
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.
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
Cited in
(85)- Linear space adaptive data structures for planar range reporting
- Two approaches to building time-windowed geometric data structures
- Near-optimal search time in \(\delta \)-optimal space, and vice versa
- Independent range sampling, revisited
- Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
- Approximating Distance Measures for the Skyline
- Dictionary matching with a few gaps
- Fast local searches and updates in bounded universes
- Dynamic geometric data structures via shallow cuttings
- Succinct indices for path minimum, with applications
- Orthogonal range searching in linear and almost-linear space
- Dictionary matching with uneven gaps
- scientific article; zbMATH DE number 7651193 (Why is no real title available?)
- On reporting the \(L_1\) metric closest pair in a query rectangle
- 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
- A linear-space data structure for range-LCP queries in poly-logarithmic time
- Optimal deterministic shallow cuttings for 3-d dominance ranges
- Submatrix maximum queries in Monge matrices are equivalent to predecessor search
- On constant factors in comparison-based geometric algorithms and data structures
- Fast construction of wavelet trees
- Less space: indexing for queries with wildcards
- Time-optimal top-\(k\) document retrieval
- Extracting powers and periods in a word from its runs structure
- Compressed indexes for text with wildcards
- Space-efficient data-analysis queries on grids
- Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in \(\mathbb R^3\)
- Skyline Computation with Noisy Comparisons
- Substring range reporting
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries
- Orthogonal point location and rectangle stabbing queries in 3-d
- The heaviest induced ancestors problem revisited
- Adaptive data structures for 2D dominance colored range counting
- Finding a Maximum Clique in a Grounded 1-Bend String Graph
- Time windowed data structures for graphs
- Top-\(k\) document retrieval in optimal time and linear space
- Range LCP
- 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
- Compact binary relation representations with rich functionality
- scientific article; zbMATH DE number 7559224 (Why is no real title available?)
- The range 1 query (R1Q) problem
- Elastic-degenerate string matching with 1 error
- Towards an optimal method for dynamic planar point location
- Composite repetition-aware data structures
- Two-dimensional range successor in optimal time and almost linear space
- Fast string dictionary lookup with one error
- Grammar-compressed indexes with logarithmic search time
- Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
- Ranked document selection
- Orthogonal range searching for text indexing
- Elastic-degenerate string matching with 1 error or mismatch
- Succinct and Implicit Data Structures for Computational Geometry
- Deterministic rectangle enclosure and offline dominance reporting on the RAM
- Sorted range reporting
- Internal shortest absent word queries in constant time and linear space
- 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
- Time-space trade-offs for Lempel-Ziv compressed indexing
- Compressed text indexing with wildcards
- Generalized substring compression
- Wavelet trees for all
- Fast relative Lempel-Ziv self-index for similar sequences
- Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads
- Universal compressed text indexing
- On position restricted substring searching in succinct space
- Dictionary matching with a bounded gap in pattern or in text
- Connectivity oracles for graphs subject to vertex failures
- Path queries on functions
- A self-index on block trees
- The fine-grained complexity of multi-dimensional ordering properties
- A simple grammar-based index for finding approximately longest common substrings
- On approximate colored path counting
- Cache-oblivious data structures for orthogonal range searching
- 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)
