×

zbMATH — the first resource for mathematics

Hypergeometrics and the cost structure of quadtrees. (English) Zbl 0834.68013
Summary: Several characteristic parameters of randomly grown quadtrees of any dimension are analyzed. Additive parameters have expectations whose generating functions are expressible in terms of generalized hypergeometric functions. A complex asymptotic process based of singularity analysis and integral representations akin to Mellin transforms leads to explicit values for various structure constants related to path length, retrieval costs, and storage occupation.
Reviewer: Reviewer (Berlin)

MSC:
68P05 Data structures
33C99 Hypergeometric functions
05A10 Factorials, binomial coefficients, combinatorial functions
05A15 Exact enumeration problems, generating functions
Keywords:
quadtrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Comtet, Advanced Combinatorics (1974) · doi:10.1007/978-94-010-2196-8
[2] Devroye, A note on the expected height of binary search trees, J. ACM 33 pp 489– (1986) · Zbl 0741.05062
[3] Devroye, Branching processes in the analysis of the heights of trees, Acta Inf. 24 pp 277– (1987) · Zbl 0643.60065 · doi:10.1007/BF00265991
[4] Devroye, An analysis of random d-dimensional quad trees, SIAM J. Comput. 19 pp 821– (1990) · Zbl 0711.68032
[5] Dingle, Asymptotic Expansions: Their Derivation and Interpretation (1973) · Zbl 0279.41030
[6] Erdélyi, Higher Transcendental Functions 1-3 (1981) · Zbl 0542.33001
[7] Finkel, Quad trees, a data structure for retrieval on composite keys, Acta Inf. 4 pp 1– (1974) · Zbl 0278.68030
[8] Flajolet, Search costs in quadtrees and singularity perturbation asymptotics, Discrete Comput. Geom. 12 pp 151– (1994)
[9] Flajolet, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (2) pp 216– (1990) · Zbl 0712.05004
[10] Flajolet, Generalized digital trees and their difference-differential equations, Random Struct. Alg. 3 pp 305– (1992) · Zbl 0758.60015
[11] Flajolet, Mellin transforms and asymptotics: finite differences and Rice’s integrals, Research Report 2031, Institut National De Recherche en Informatique et en Automatique, Theor. Comput. Sci. (1994) · Zbl 0869.68056
[12] Flajolet, Analytic variations on quadtrees, Algorithmica 10 pp 473– (1993) · Zbl 0783.68056
[13] Ford, Studies on Divergent Series and Summability and the Asymptotic Developments of Functions Defined by Maclaurin Series (1960)
[14] Gasper, Basic Hypergeometric Series, Vol. 35 of Encyclopedia of Mathematics and Its Applications (1990)
[15] Gonnet, Handbook of Algorithms and Data Structures (1984)
[16] Gonnet, Handbook of Algorithms and Data Structures: in Pascal and C (1991) · Zbl 0665.68001
[17] Hardy, Ramanujan: Twelve Lectures on Subjects Suggested by his Life and Work (1978) · JFM 67.0002.09
[18] Twelve Lectures on Subjects Suggested by his Life and Work (1940) · JFM 67.0002.09
[19] Hoshi, Page usage in a quadtree index, BIT 32 pp 384– (1992) · Zbl 0752.68019
[20] Iwasaki, From Gauss to Painlevé-A Modern Theory of Special Functions, Aspects of Mathematics (1991)
[21] Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (1973) · Zbl 0302.68010
[22] G. Labelle L. Laforest Étude de constantes universelles pour les arborescences hyperquaternaires de recherche Proc. 5th FPSAC Conference 1993 89 98 · Zbl 0853.05007
[23] Labelle, Combinatorial variations on multidimensional quadtrees, J. Combinat. Theory Ser. A · Zbl 0815.05002
[24] L. Laforest 1990
[25] Lindelöf, Collection de Monographies sur la Théorie des Fonctions, Publiée sous la Direction de M. Émile Borel (1905)
[26] Collection de Monographies sur la Théorie des Fonctions, Publiée sous la Direction de M. Émile Borel (1989)
[27] Mahmoud, Evolution of Random Search Trees (1992) · Zbl 0762.68033
[28] Samet, Applications of Spatial Data Structures (1990)
[29] Samet, The Design and Analysis of Spatial Data Structures (1990)
[30] Slater, Generalized Hypergeometric Functions (1966) · Zbl 0135.28101
[31] Whittaker, A Course of Modern Analysis (1927)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.