Quadtree

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.

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.