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

DOI10.1016/J.IPL.2015.09.002MaRDI QIDQ894470zbMATH OpenOpenAlexFDO

Authors 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

computational geometrydata structuresplanar orthogonal skyline reportingrange successorsorted range reporting

Mathematics Subject Classification ID

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

Recommendations

• Orthogonal Range Searching in Linear and Almost-Linear Space
• Efficient Data Structures for the Orthogonal Range Successor Problem
• Orthogonal range searching in linear and almost-linear space
• Improved data structures for the orthogonal range successor problem
• On space efficient two dimensional range minimum data structures

Cites work

• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• I/O-efficient 2-d orthogonal range skyline and attrition priority queues
• Improved data structures for the orthogonal range successor problem
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• Optimal planar orthogonal skyline counting queries
• Orthogonal range searching for text indexing
• Orthogonal range searching on the RAM, revisited
• Sorted range reporting
• Space-efficient preprocessing schemes for range minimum queries on static arrays

Cited in

(10)

• 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
• The heaviest induced ancestors problem revisited
• Efficient Data Structures for the Orthogonal Range Successor Problem
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Improved data structures for the orthogonal range successor problem
• Internal pattern matching queries in a text and applications
• Path and ancestor queries over trees with multidimensional weight vectors

This page was built for publication: Two-dimensional range successor in optimal time and almost linear space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q894470)