Orthogonal range searching in linear and almost-linear space

DOI10.1016/j.comgeo.2008.09.001zbMath1170.68012MaRDI 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 structures; geometric data structures; orthogonal range searching

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

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, Towards optimal range medians, Untangled monotonic chains and adaptive range search, Improved data structures for the orthogonal range successor problem, Dynamic path queries in linear space, The fine-grained complexity of multi-dimensional ordering properties, Compressed text indexing with wildcards, Array Range Queries, Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing, Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search

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