Premium
Hypergeometrics and the cost structure of quadtrees
Author(s) -
Flajolet Philippe,
Labelle Gilbert,
Laforest Louise,
Salvy Bruno
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240070203
Subject(s) - dimension (graph theory) , mellin transform , hypergeometric function , singularity , mathematics , hypergeometric distribution , path (computing) , pure mathematics , constant (computer programming) , gravitational singularity , algebra over a field , mathematical analysis , computer science , laplace transform , programming language
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.