Combinatorial variations on multidimensional quadtrees (Q1344226)

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.