A tree having four branches at each node. Quadtrees are used in the construction of some multidimensional databases (e.g., cartography, computer
graphics, and image processing). For a 
-dimensional tree, the expected number of comparisons over
all pairs of integers for successful and unsuccessful searches are known analytically
for 
and numerically for 
.
Quadtree
Explore with Wolfram|Alpha
References
de Berg, M.; van Kreveld, M.; Overmans, M.; and Schwarzkopf, O. "Quadtrees: Non-Uniform Mesh Generation." Ch. 14 in Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin:Springer-Verlag, pp. 291-306, 2000.Finkel, R. A. and Bentley, J. L. "Quad Trees, a Data Structure for Retrieval on Composite Keys." Acta Informatica 4, 1-9, 1974.Flajolet, P.; Gonnet, G.; Puech, C.; and Robson, J. M. "Analytic Variations on Quadtrees." Algorithmica 10, 473-500, 1993.Flajolet, P.; Labelle, G.; Laforest, L.; and Salvy, B. "Hypergeometrics and the Cost Structure of Quadtrees." Random Structure Alg. 7, 117-144, 1995. http://algo.inria.fr/flajolet/Publications/publist.html.Gonnet, G. H. and Baeza-Yates, R. Ch. 3 in Handbook of Algorithms and Data Structures in Pascal and C. Reading, MA: Addison-Wesley, 1991.Lauwerier, H. Fractals: Endlessly Repeated Geometric Figures. Princeton, NJ: Princeton University Press, pp. 11-13, 1991.Samet, H. Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS. Reading, MA: Addison-Wesley, 1989.Samet, H. The Design and Analysis of Spatial Data Structures. Reading, MA: Addison-Wesley, 1990.Referenced on Wolfram|Alpha
QuadtreeCite this as:
Weisstein, Eric W. "Quadtree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Quadtree.html