Combinatorial variations on multidimensional quadtrees (Q1344226): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0097-3165(95)90103-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2048049795 / rank | |||
Normal rank |
Revision as of 22:27, 19 March 2024
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