SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS

DOI10.1142/S0218195908002568zbMath1149.68371OpenAlexW2105246008MaRDI QIDQ3521595

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)

Related Items (7)

Processing succinct matrices and vectors ⋮ Quad-\(k\mathrm d\) trees: a general framework for \(k\mathrm d\) trees and quad trees ⋮ REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION ⋮ Bounds on the cost of compatible refinement of simplex decomposition trees in arbitrary dimensions ⋮ The Online House Numbering Problem: Min-Max Online List Labeling ⋮ Faster compressed quadtrees ⋮ Dynamic smooth compressed quadtrees

Cites Work

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

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