The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data
<|reference_start|>The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data: 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.<|reference_end|>
@article{eppstein2005the,
    title={The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional
  Data},
    author={David Eppstein, Michael T. Goodrich, Jonathan Z. Sun},
    journal={arXiv preprint arXiv:cs/0507049},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0507049},
    primaryClass={cs.CG}
}