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 tree, the expected number of comparisons over all pairs of integers for successful and unsuccessful searches are given analytically for and numerically for by Finch.

**References**

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/qdt/qdt.html

Flajolet, P.; Gonnet, G.; Puech, C.; and Robson, J. M. ``Analytic Variations on Quadtrees.'' *Algorithmica*
**10**, 473-500, 1993.

Lauwerier, H. *Fractals: Endlessly Repeated Geometric Figures.* Princeton, NJ: Princeton University Press, pp. 11-13, 1991.

© 1996-9

1999-05-25