Around the root of random multidimensional quadtrees

DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Around the root of random multidimensional quadtrees

Gilbert Labelle, Louise Laforest, Xavier Provençal

Abstract

We analyse the distribution of the root pattern of randomly grown multidimensional point quadtrees. In particular, exact, recursive and asymptotic formulas are given for the expected arity of the root.

Full Text: PDF