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

DOI10.1016/j.ipl.2015.09.002zbMath1347.68105OpenAlexW2189845893MaRDI 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

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items

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

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