Combinatorial variations on multidimensional quadtrees (Q1344226)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Combinatorial variations on multidimensional quadtrees |
scientific article |
Statements
Combinatorial variations on multidimensional quadtrees (English)
0 references
11 June 1995
0 references
The quadtrees were introduced by \textit{A. F. Finkel} and \textit{J. L. Bentley} [Acta Inform. 4, 1-9 (1974; Zbl 0278.68030)] and \textit{H. Samet} [Comput. Surveys 16, 187-260 (1984)] as a generalization of binary search trees. The authors present a parallel study of three models of multidimensional quadtrees---quadtrees of Catalan's type, increasing quadtrees and point quadtrees, using the language of the theory of species. Combinatorial equations for these structures are obtained that lead to explicit, recursive and asymptotic formulas for the probability of having \(k\) nodes in a fixed hyperoctant, the expected value and the variance of the number of leaves.
0 references
quadtrees
0 references
species
0 references
asymptotic formulas
0 references