ISSN:
1432-0541
Keywords:
Analysis of algorithms
;
Multidimensional search
;
Quadtrees
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Quadtrees constitute a hierarchical data structure which permits fast access to multidimensional data. This paper presents the analysis of the expected cost of various types of searches in quadtrees — fully specified and partial-match queries. The data model assumes random points with independently drawn coordinate values. The analysis leads to a class of “full-history” divide-and-conquer recurrences. These recurrences are solved using generating functions, either exactly for dimensiond=2, or asymptotically for higher dimensions. The exact solutions involve hypergeometric functions. The general asymptotic solutions rely on the classification of singularities of linear differential equations with analytic coefficients, and on singularity analysis techniques. These methods are applicable to the asymptotic solution of a wide range of linear recurrences, as may occur in particular in the analysis of multidimensional searching problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01891833
Permalink