Orthogonal Range Searching in Linear and Almost-Linear Space

DOI10.1007/978-3-540-73951-7_3zbMATH Open1209.68162OpenAlexW1873288469MaRDI QIDQ3603510FDOQ3603510

Authors: Yakov Nekrich 

Publication date: 17 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73951-7_3

Recommendations

• Orthogonal range searching in linear and almost-linear space
• A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
• Space efficient dynamic orthogonal range reporting
• Space efficient dynamic orthogonal range reporting
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting

Mathematics Subject Classification ID

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

Cited In (29)

• Efficient data structures for range searching on a grid
• 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
• Space efficient dynamic orthogonal range reporting
• Orthogonal range searching in linear and almost-linear space
• Colored Range Searching in Linear Space
• Untangled monotonic chains and adaptive range search
• Light orthogonal networks with constant geometric dilation
• Optimal static range reporting in one dimension
• Orthogonal range searching on the RAM, revisited
• Algorithms for indexing highly similar DNA sequences
• Efficient dynamic range searching using data replication
• Linear space data structures for two types of range search
• Space-efficient data-analysis queries on grids
• Array range queries
• Space-efficient data-analysis queries on grids
• Quasi-optimal range searching in spaces of finite VC-dimension
• Space efficient dynamic orthogonal range reporting
• Adaptive and approximate orthogonal range counting
• Linear-space data structures for range mode query in arrays
• Two-dimensional range successor in optimal time and almost linear space
• Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
• A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
• Adaptive and approximate orthogonal range counting
• Compact and succinct data structures for multidimensional orthogonal range searching
• Non-orthogonal homothetic range partial-sum query on integer grids (extended abstract)
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• 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 Q3603510)