Around the root of random multidimensional quadtrees

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.

Keywords

• point quadtrees
• asymptotics
• random structures.
• [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]