SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS

DOI10.1142/S0218195908002568MaRDI QIDQ3521595zbMATH OpenOpenAlexFDO

Authors David Eppstein, Jonathan Z. Sun, Michael T. Goodrich

Publication date 26 August 2008

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195908002568

zbMATH Keywords

multi-dimensional data structureskip octree

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• The skip quadtree
• A dynamic data structure for approximate range searching
• A deterministic skip list for \(k\)-dimensional range search
• Quad-K-d trees
• Quad-k d trees: a general framework for k d trees and quad trees

Cites work

• A deterministic skip list for \(k\)-dimensional range search
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Approximate closest-point queries in high dimensions
• Approximate range searching
• Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees
• Dynamic data structures for fat objects and their applications
• Foundations of multidimensional and metric data structures.
• Multidimensional binary search trees used for associative searching
• On the union of fat wedges and separating a collection of segments by a line
• Squarish \(k\)-\(d\) trees

Cited in

(15)

• A deterministic skip list for \(k\)-dimensional range search
• Faster compressed quadtrees
• A self-adjusting data structure for multidimensional point sets
• REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION
• scientific article; zbMATH DE number 177545 (Why is no real title available?)
• scientific article; zbMATH DE number 917638 (Why is no real title available?)
• The online house numbering problem: min-max online list labeling
• Dynamic smooth compressed quadtrees
• Skip-webs, efficient distributed data structures for multi-dimensional data sets
• The skip quadtree
• A dynamic data structure for approximate range searching
• 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
• An O(n n) algorithm for single-source shortest paths in disk graphs
• Quad-k d trees: a general framework for k d trees and quad trees

This page was built for publication: SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS

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