A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES

DOI10.1142/S0218195909002800MaRDI QIDQ3628098zbMATH OpenOpenAlexFDO

Authors Yakov Nekrich

Publication date 19 May 2009

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195909002800

zbMATH Keywords

data structuresdynamic data structuresorthogonal range reporting

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Orthogonal Range Searching in Linear and Almost-Linear Space
• Orthogonal range searching in linear and almost-linear space
• Space efficient dynamic orthogonal range reporting
• Space efficient dynamic orthogonal range reporting
• Orthogonal range searching on the RAM, revisited

Cites work

• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• A class of algorithms which require nonlinear time to maintain disjoint sets
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• Cache-Oblivious B-Trees
• Design and implementation of an efficient priority queue
• Divided \(k-d\) trees
• Fully Dynamic Orthogonal Range Reporting on RAM
• Multidimensional divide-and-conquer
• Optimal External Memory Interval Management
• Preserving order in a forest in less than logarithmic time and linear space
• Universal codeword sets and representations of the integers

Cited in

(7)

• Linear space adaptive data structures for planar range reporting
• Orthogonal range searching in linear and almost-linear space
• Fully Dynamic Orthogonal Range Reporting on RAM
• Orthogonal Range Searching in Linear and Almost-Linear Space
• Time-optimal top-\(k\) document retrieval
• Reporting and counting maximal points in a query orthogonal rectangle
• Top-\(k\) document retrieval in optimal time and linear space

This page was built for publication: A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES

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