Hypergeometrics and the cost structure of quadtrees
- 1 September 1995
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 7 (2) , 117-144
- https://doi.org/10.1002/rsa.3240070203
Abstract
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 on 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.This publication has 12 references indexed in Scilit:
- Search costs in quadtrees and singularity perturbation asymptoticsDiscrete & Computational Geometry, 1994
- Analytic variations on quadtreesAlgorithmica, 1993
- Page usage in a quadtree indexBIT Numerical Mathematics, 1992
- Generalized Digital Trees and Their Difference—Differential EquationsRandom Structures & Algorithms, 1992
- An Analysis of Randomd-Dimensional Quad TreesSIAM Journal on Computing, 1990
- Singularity Analysis of Generating FunctionsSIAM Journal on Discrete Mathematics, 1990
- Branching processes in the analysis of the heights of treesActa Informatica, 1987
- A note on the height of binary search treesJournal of the ACM, 1986
- Advanced CombinatoricsPublished by Springer Nature ,1974
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974