Orthogonal range searching in linear and almost-linear space
From MaRDI portal
Publication:1005331
DOI10.1016/j.comgeo.2008.09.001zbMath1170.68012MaRDI QIDQ1005331
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
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