info prev up next book cdrom email home


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$-D tree, the expected number of comparisons over all pairs of integers for successful and unsuccessful searches are given analytically for $d=2$ and numerically for $d\geq 3$ by Finch.


Finch, S. ``Favorite Mathematical Constants.''

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 Eric W. Weisstein