A dynamic data structure for approximate range searching

DOI10.1145/1810959.1811002MaRDI QIDQ5405889zbMATH OpenOpenAlexFDO

Authors David M. Mount, Eunhui Park

Publication date 3 April 2014

Published in Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1810959.1811002

zbMATH Keywords

approximation algorithmsdynamic data structuresgeometric data structuresquadtreesrange searching

Mathematics Subject Classification ID

Combinatorial complexity of geometric structures (52C45) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• The skip quadtree
• Approximate range searching
• SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
• Space-time tradeoffs for approximate spherical range counting
• Approximate Range Searching in External Memory

Cited in

(17)

• Divided \(k-d\) trees
• Fixed queries array: A fast and economical data structure for proximity searching
• Conic nearest neighbor queries and approximate Voronoi diagrams
• Opportunistic data structures for range queries
• Crushing disks efficiently
• Space-time tradeoffs for approximate spherical range counting
• An optimal dynamic interval stabbing-MAX data structure?
• Dynamic range majority data structures
• Fully retroactive approximate range and nearest neighbor searching
• SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS
• Approximate Range Searching: The Absolute Model
• scientific article; zbMATH DE number 1953879 (Why is no real title available?)
• Approximate Range Searching in External Memory
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Efficient regular data structures and algorithms for dilation, location, and proximity problems
• Bounds on the cost of compatible refinement of simplex decomposition trees in arbitrary dimensions
• Sparse higher order Čech filtrations

This page was built for publication: A dynamic data structure for approximate range searching

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