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 d-dimensional tree, the expected number of comparisons over all pairs of integers for successful and unsuccessful searches are known analytically for d=2 and numerically for d>=3.

Explore with Wolfram|Alpha


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., 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


Cite this as:

Weisstein, Eric W. "Quadtree." From MathWorld--A Wolfram Web Resource.

Subject classifications