ANALYTIC VARIATIONS ON QUADTREES

Quadtrees constitute a hierarchical data structure which permits fast access to multidimensional data. This paper presents the analysis of t he expected cost of various types of searches in quadtrees-fully speci fied and partial-match queries. The data model assumes random points w ith independently drawn coordinate values. The analysis leads to a cla ss of ''full-history'' divide-and-conquer recurrences. These recurrenc es are solved using generating functions, either exactly for dimension d = 2, or asymptotically for higher dimensions. The exact solutions i nvolve hypergeometric functions. The general asymptotic solutions rely on the classification of singularities of linear differential equatio ns with analytic coefficients, and on singularity analysis techniques. These methods are applicable to the asymptotic solution of a wide rang e of linear recurrences, as may occur in particular in the analysis of multidimensional searching problems.