Two-dimensional range successor in optimal time and almost linear space

DOI10.1016/j.ipl.2015.09.002zbMath1347.68105MaRDI QIDQ894470

Gelin Zhou

Publication date: 1 December 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.09.002

zbMATH Keywords

data structurescomputational geometryplanar orthogonal skyline reportingrange successorsorted range reporting

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

The Heaviest Induced Ancestors Problem Revisited, Unnamed Item, Smallest \(k\)-enclosing rectangle revisited, The heaviest induced ancestors problem: better data structures and applications, Two approaches to building time-windowed geometric data structures, Gapped indexing for consecutive occurrences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved data structures for the orthogonal range successor problem
• I/O-efficient 2-d orthogonal range skyline and attrition priority queues
• Orthogonal Range Searching for Text Indexing
• Sorted Range Reporting
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Optimal Planar Orthogonal Skyline Counting Queries
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
• Orthogonal range searching on the RAM, revisited