Back to Search
Start Over
SKIP QUADTREES:: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS.
- Source :
- International Journal of Computational Geometry & Applications; Apr2008, Vol. 18 Issue 1/2, p131-160, 30p, 8 Diagrams
- Publication Year :
- 2008
-
Abstract
- We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R<superscript>2</superscript>) or the skip octree (for point data in R<superscript>d</superscript>, 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 logarithmic-height 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- GEOMETRY
MATHEMATICS
ALGORITHMS
ALGEBRA
ALGEBRAIC geometry
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 18
- Issue :
- 1/2
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 31220545
- Full Text :
- https://doi.org/10.1142/S0218195908002568