Orthogonal range searching in linear and almost-linear space
From MaRDI portal
Publication:1005331
DOI10.1016/J.COMGEO.2008.09.001zbMATH Open1170.68012OpenAlexW2028689405MaRDI QIDQ1005331FDOQ1005331
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
Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Multidimensional divide-and-conquer
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Preserving order in a forest in less than logarithmic time and linear space
- Optimal static range reporting in one dimension
- Divided \(k-d\) trees
- Should Tables Be Sorted?
- Universal codeword sets and representations of the integers
- Design and implementation of an efficient priority queue
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Optimal External Memory Interval Management
- Space efficient dynamic orthogonal range reporting
- Cache-Oblivious B-Trees
- On dynamic range reporting in one dimension
- A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
- Fully Dynamic Orthogonal Range Reporting on RAM
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (22)
- The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching
- Untangled monotonic chains and adaptive range search
- Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back
- Towards optimal range medians
- Efficient Data Structures for the Orthogonal Range Successor Problem
- Colored Range Searching in Linear Space
- On the difficulty of range searching
- Orthogonal range searching on the RAM, revisited
- Space-efficient data-analysis queries on grids
- Quasi-optimal range searching in spaces of finite VC-dimension
- Improved data structures for the orthogonal range successor problem
- Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
- Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search
- Dynamic path queries in linear space
- Array Range Queries
- Compact and succinct data structures for multidimensional orthogonal range searching
- Non-orthogonal homothetic range partial-sum query on integer grids (extended abstract)
- Compressed text indexing with wildcards
- Sublinear time Lempel-Ziv (LZ77) factorization
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- The fine-grained complexity of multi-dimensional ordering properties
- Space efficient data structures for dynamic orthogonal range counting
This page was built for publication: Orthogonal range searching in linear and almost-linear space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1005331)
