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

DOI10.1016/J.IPL.2015.09.002zbMATH Open1347.68105OpenAlexW2189845893MaRDI QIDQ894470FDOQ894470

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

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

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)

Cites Work

• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Orthogonal Range Searching for Text Indexing
• Orthogonal range searching on the RAM, revisited
• Sorted range reporting
• Optimal Planar Orthogonal Skyline Counting Queries
• Title not available (Why is that?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Improved data structures for the orthogonal range successor problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• I/O-efficient 2-d orthogonal range skyline and attrition priority queues

Cited In (9)

• Two approaches to building time-windowed geometric data structures
• The Heaviest Induced Ancestors Problem Revisited
• Title not available (Why is that?)
• Efficient Data Structures for the Orthogonal Range Successor Problem
• Smallest \(k\)-enclosing rectangle revisited
• The heaviest induced ancestors problem: better data structures and applications
• Improved data structures for the orthogonal range successor problem
• Internal pattern matching queries in a text and applications
• Gapped indexing for consecutive occurrences

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)