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

Simple item page
dc.creatorEppstein, David
dc.creatorGoodrich, Michael T.
dc.creatorSun, Jonathan Z.
dc.date2005-07-19
dc.date.accessioned2026-07-07T03:23:14Z
dc.date.available2026-07-07T03:23:14Z
dc.descriptionWe 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.
dc.description12 pages, 3 figures. A preliminary version of this paper appeared in the 21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 296-305
dc.identifierhttps://arxiv.org/abs/cs/0507049
dc.identifierhttp://arxiv.org/abs/cs/0507049
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32865
dc.subjectComputational Geometry
dc.subjectF.2.2
dc.titleThe Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data
dc.typetext

Files

Collections

arXiv