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

@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.}, archivePrefix = {arXiv}, author = {Eppstein, David and Goodrich, Michael T. and Sun, Jonathan Z.}, citeulike-article-id = {261508}, citeulike-linkout-0 = {http://arxiv.org/abs/cs.CG/0507049}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs.CG/0507049}, comment = {appeared in socg 2005}, day = {19}, eprint = {cs.CG/0507049}, keywords = {decomposition, quadtree, structure}, month = {Jul}, posted-at = {2005-10-07 05:52:11}, priority = {4}, title = {The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data}, url = {http://arxiv.org/abs/cs.CG/0507049}, year = {2005} }

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