The Skip Quadtree: A Simple DynamicData Structure for Multidimensional DataDavid Eppstein Michael T. Goodrich†Jonathan Z. Sun†Department of Computer ScienceDonald Bren School of Information and Computer SciencesUniversity of California, IrvineIrvine, CA 92697-3425, USA{eppstein,goodrich,zhengsun}(at)ics.uci.eduABSTRACTWe present a new multi-dimensional data structure, which we callthe skip quadtree (for point data in R2) or the skip octree (for pointdata in Rd, with constant d > 2). Our data structure combinesthe best features of two well-known data structures, in that it hasthe well-defined “box”-shaped regions of region quadtrees and thelogarithmic-height search and update hierarchical structure of skiplists. Indeed, the bottom level of our structure is exactly a regionquadtree (or octree for higher dimensional data). We describe effi-cient algorithms for inserting and deleting points in a skip quadtree,as well as fast methods for performing point location, approximaterange, and approximate nearest neighbor queries.Categories and Subject DescriptorsE.1 [Data]: Data Structures; F.2.2 [Analysis of Algorithms andProblemComplexity]: Nonnumerical Algorithmsand Problems—geometrical problems and computations; H.3.3 [Information Sys-tems]: Information Storage and Retrieval—information search andretrievalGeneral TermsAlgorithms, TheoryKeywordsSkip quadtree, quadtree, octree, dynamic data structure, point loca-tion, range, nearest neighbor, approximation algorithm.1. INTRODUCTIONData structures for multidimensional point data are of signif-icant interest in the computational geometry, computer graphics,and scientific data visualization literatures. They allow point datato be stored and searched efficiently, for example to perform rangequeries to count or report (possibly approximately) the points that†Supported by NSF Grants CCR-0225642, CCR-0311720, CCR-0312760, and DUE-0231467.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SCG’05, June 6–8, 2005, Pisa, Italy.Copyright 2005 ACM 1-58113-991-8/05/0006 ...$5.00.are contained in a given query region. We are interested in thispaper in data structures for multidimensional point sets that are dy-namic, in that they allow for fast point insertion and deletion, aswell as efficient, in that they use linear space and allow for fastquery times.1.1 Related Previous WorkLinear-space multidimensional data structures typically are de-fined by hierarchical subdivisions of space, which give rise to tree-based search structures. That is, a hierarchy is defined by associ-ating with each node v in a tree T a region R(v) in Rdsuch thatthe children of v are associated with subregions of R(v) defined bysome kind of “cutting” action on R(v). Examples include:• quadtrees [32]: regions are defined by squares in the plane,which are subdivided into four equal-sized squares for anyregions containing more than a single point. (These are alsocalled PR quadtrees, and we always refer to this variant ofquadtrees in this paper.) So each internal node in the under-lying tree has four children and regions have optimal aspectratios (which is useful for many types of queries). Unfortu-nately, the tree can have arbitrary depth, independent evenof the number of input points. Even so, point insertion anddeletion is fairly simple.• octrees [22, 32]: regions are defined by hypercubes in Rd,which are subdivided into 2dequal-sized hypercubes for anyregions containing more than a single point. So each in-ternal node in the underlying tree has 2dchildren and, likequadtrees, regions have optimal aspect ratios and point inser-tion/deletion is simple, but the tree can have arbitrary depth.• k-d trees [10]: regions are defined by hyperrectangles in Rd,which are subdivided into two hyperrectangles using an axis-perpendicular cutting hyperplane through the median point,for any regions containing more than two points. So the un-derlying tree can be made a balanced binary tree with logn depth for a static set of points. Unfortunately, the regions canhave arbitrarily large aspect ratios, which can adversely af-fect the efficiencies of some queries. Although some variantswere proposed to help, such as by cutting along the longestside instead of along each axis recursively [15], they onlyimprove the aspect ratios experimentally or statistically. Inaddition, maintaining an efficient k-d tree subject to point in-sertions and removal is non-trivial.• compressed quad/octrees [2, 11–13]: regions are defined inthe same way as in a quadtree or octree (depending on thedimensionality), but paths in the tree consisting of nodes withonly one non-empty child are compressed to single edges.296This compression allows regions to still be hypercubes (withoptimal aspect ratio), but it changes the subdivision processfrom a four-way cut to a reduction to at most four disjointhypercubes inside the region. It also forces the height of the(compressed) quad/octree to be at most O(n). This heightbound is still not very efficient, of course.• balanced box decomposition (BBD) trees [6–8]: regions aredefined by hypercubes with smaller hypercubes subtractedaway, so that the height of the decomposition tree is O(logn).These regions have good aspect ratios, that is, they are “fat”[20,21], but they are not convex, which limits some of the ap-plications of this structure. In addition, making this structuredynamic appears non-trivial.• balanced aspect-ratio (BAR) trees [17, 19]: regions are de-fined by convex polytopes of bounded aspect ratio, whichare subdivided by hyperplanes perpendicular to one of a setof 2d “spread-out” vectors so that the height of the decom-position tree is O(logn). This structure has the advantage ofhaving convex regions and logarithmic depth, but the regionsare no longer hyperrectangles (or even hyperrectangles withhyperrectangular “holes”). In addition, making this structuredynamic appears non-trivial.This summary is, of course, not a complete review of existing workon space partitioning data structures for multidimensional pointsets. The reader interested in further study of these topics is