Quadtrees (and Family)
Hierarchical regular-decomposition structures; Hierarchical spatial indexes; Quadtree variations
In general, the term quadtree refers to a class of representations of geometric entities (such as points, line segments, polygons, regions) in a space of two (or more) dimensions that recursively decompose the space containing these entities into blocks until the data in each block satisfy some condition (with respect, for example, to the block size, the number of block entities, the characteristics of the block entities, etc.).
In a more restricted sense, the term quadtree (octree) refers to a tree data structure in which each internal node has four (eight) children and is used for the representation of geometric entities in a two (three) dimensional space. The root of the tree represents the whole space/region. Each child of a node represents a subregion of the subregion of its parent. The subregions of the siblings constitute a partition of the parent’s regions.
- 2.Samet H. The design and analysis of spatial data structures. Reading: Addison Wesley; 1990.Google Scholar
- 6.Manouvrier M, Rukoz M, Jomier G. Quadtree-based image representation and retrieval. In: Spatial databases: technologies, techniques and trends. Hershey: Idea Group Publishing; 2005. p. 81–106.Google Scholar
- 9.Eppstein D, Goodrich MT, Sun JZ. The skip quadtree: a simple dynamic data structure for multidimensional data. In: Proceedings of the 21st Annual Symposium on Computational Geometry; 2005. p. 296–305.Google Scholar
- 10.Kothuri R, Ravada S, Abugov D. Quadtree and r-tree. indexes in oracle spatial: a comparison using gis data. In: Proceedings of the ACM SIGMOD Inter-national Conference on Management of Data; 2002. p. 546–57.Google Scholar
- 11.Brabec F, Samet H. Spatial index demos. http://donar.umiacs.umd.edu/quadtree/index.html. Last accessed in Dec 2016.
- 12.Samet H. Applications of spatial data structures. Reading: Addison Wesley; 1990.Google Scholar
- 14.Kim YJ, Patel JM. Rethinking choices for multi-dimensional point indexing: making the case for the often ignored quadtree. In: Proceedings of the 3rd Biennial Conference on Innovative Data Systems Research; 2007. p. 281–91. http://cidrdb.org/2007Proceedings.zip
- 15.Vassilakopoulos M, Manolopoulos Y. External balanced regular (x-BR) trees: new structures for very large spatial databases. In: Fotiadis DI, Nikolopoulos SD, editors. Advances in informatics. Singapore: World Scientific; 2000. p. 324–33.Google Scholar