Skip Quadtrees: Dynamic Data Structures for Multidimensional Point Sets
Document Type
Article
Publication Date
4-1-2008
Department
Computing
School
Computing Sciences and Computer Engineering
Abstract
We present a new multi-dimensional data structure, which we call the skip quadtree ( for point data in R-2) or the skip octree (for point data in R., with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmicheight search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.
Publication Title
International Journal of Computational Geometry & Applications
Volume
18
Issue
41276
First Page
131
Last Page
160
Recommended Citation
Eppstein, D.,
Goodridge, M. T.,
Sun, J. Z.
(2008). Skip Quadtrees: Dynamic Data Structures for Multidimensional Point Sets. International Journal of Computational Geometry & Applications, 18(41276), 131-160.
Available at: https://aquila.usm.edu/fac_pubs/1653