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

by: David Eppstein, Michael T Goodrich, Jonathan Z Sun

(19 Jul 2005)

View FullText article

arXiv (abstract), arXiv (PDF)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

ansobol, yalding, jrw, zzkt, rahul, balicea, syoyo, tshr, krissp, gane5h, Kazuki, whym, SRL (group), weymouth

Find related articles with these CiteULike tags

3d, algorithm, algorithms, applied-math, approximate-search, computation, computational-geometry, computing, control-theory, datastructure, data-structure, data-structures, decomposition, geomancy, geometry, graphs, k-d-tree, modeling-and-simulation, no-tag, quadtree, structure, voxelization

Résumé

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.

@misc{citeulike:261508, 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^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.}, author = {Eppstein, David and Goodrich, Michael T. and Sun, Jonathan Z. }, citeulike-article-id = {261508}, eprint = {cs.CG/0507049}, keywords = {computing, geomancy}, month = {Jul}, posted-at = {2005-12-09 18:22:15}, priority = {2}, title = {The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data}, url = {http://arxiv.org/abs/cs.CG/0507049}, year = {2005} }

RIS record

TY - ELEC ID - citeulike:261508 L3 - citeulike-article-id:261508 TI - The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data N2 - 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. KW - computing KW - geomancy AU - Eppstein, David AU - Goodrich, Michael AU - Sun, Jonathan PY - 2005/Jul/19/ UR - http://arxiv.org/abs/cs.CG/0507049 ER -

RIS BibTeX