Orthogonal range searching in linear and almost-linear space

DOI10.1016/j.comgeo.2008.09.001zbMath1170.68012OpenAlexW2028689405MaRDI QIDQ1005331

Yakov Nekrich

Publication date: 9 March 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2008.09.001

zbMATH Keywords

dynamic data structuresgeometric data structuresorthogonal range searching

Mathematics Subject Classification ID

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

Related Items (12)

Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search ⋮ Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing ⋮ Efficient Data Structures for the Orthogonal Range Successor Problem ⋮ Space efficient data structures for dynamic orthogonal range counting ⋮ Space-efficient data-analysis queries on grids ⋮ Improved data structures for the orthogonal range successor problem ⋮ Compressed text indexing with wildcards ⋮ Towards optimal range medians ⋮ Untangled monotonic chains and adaptive range search ⋮ Dynamic path queries in linear space ⋮ Array Range Queries ⋮ The fine-grained complexity of multi-dimensional ordering properties

Cites Work

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

This page was built for publication: Orthogonal range searching in linear and almost-linear space