Space efficient dynamic orthogonal range reporting

DOI10.1007/S00453-007-9030-9MaRDI QIDQ2461544zbMATH OpenOpenAlexFDO

Authors Yakov Nekrich

Publication date 28 November 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9030-9

zbMATH Keywords

Algorithms and data structuresComputational geometryDynamic data structuresOrthogonal range searching

Mathematics Subject Classification ID

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

Recommendations

• Space efficient dynamic orthogonal range reporting
• Fully Dynamic Orthogonal Range Reporting on RAM
• Dynamic orthogonal range searching on the RAM, revisited
• Orthogonal range searching in linear and almost-linear space
• Orthogonal Range Searching in Linear and Almost-Linear Space

Cites work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• A dynamic fixed windowing problem
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Applications of range query theory to relational data base join and selection operations
• Cache-Oblivious B-Trees
• Cache-oblivious data structures for orthogonal range searching
• Concatenable structures for decomposable problems
• Divided \(k-d\) trees
• Dynamic fractional cascading
• Filtering Search: A New Approach to Query-Answering
• Fully Dynamic Orthogonal Range Reporting on RAM
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 2079392 (Why is no real title available?)
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• New Data Structures for Orthogonal Range Queries
• Priority Search Trees

Cited in

(23)

• Orthogonal range searching in linear and almost-linear space
• Dynamic half-space range reporting and its applications
• Online recognition of dictionary with one gap
• Orthogonal range reporting and rectangle stabbing for fat rectangles
• Amortized bounds for dynamic orthogonal range reporting
• Efficient dynamic range searching using data replication
• Dynamic range selection in linear space
• External memory orthogonal range reporting with fast updates
• External memory orthogonal range reporting with fast updates
• A data structure for multi-dimensional range reporting
• Orthogonal Range Searching in Linear and Almost-Linear Space
• A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
• Space efficient data structures for dynamic orthogonal range counting
• scientific article; zbMATH DE number 2079392 (Why is no real title available?)
• Dynamic orthogonal range searching on the RAM, revisited
• Succinct dynamic one-dimensional point reporting
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Space Efficient Multi-dimensional Range Reporting
• Space efficient dynamic orthogonal range reporting
• Fully Dynamic Orthogonal Range Reporting on RAM
• Linear space adaptive data structures for planar range reporting
• Four-dimensional dominance range reporting in linear space
• Online list labeling: breaking the ^2n barrier

This page was built for publication: Space efficient dynamic orthogonal range reporting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2461544)