The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data

Details The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data

2005-07-19

arxiv.org/abs/cs/0507049v1

Computer Science

Computational Geometry

12 pages, 3 figures. A preliminary version of this paper appeared in the 21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 296-305

Scientific paper

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^d, 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 and approximate range queries.

Affiliated with

Also associated with

No associations

Rating

The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491172