Asymptotic Properties of Random Voronoi Cells with Arbitrary Underlying Density

Abstract

We consider the Voronoi diagram generated by $n$ i.i.d. ${\mathbb{R}}^d$-valued random variables with an arbitrary underlying probability density function $f$ on ${\mathbb{R}}^d$, and analyse the asymptotic behaviours of certain geometric properties, such as the measure, of the Voronoi cells as $n$ tends to infinity. We adapt the methods used by Devroye et al (2017) to conduct a study of the asymptotic properties of two types of Voronoi cells: 1, Voronoi cells that have a fixed nucleus; 2, Voronoi cells that contain a fixed point. For the first type of Voronoi cells, we show that their geometric properties resemble those in the case when the Voronoi diagram is generated by a homogeneous Poisson point process. For the second type of Voronoi cells, we determine the limiting distribution, which is universal in all choices of $f$, of the rescaled measure of the cells. For both types, we establish the asymptotic independence of measures of disjoint cells.

31 papges, 4 figures

References in corpus (1)

• ZOBOV: a parameter-free void-finding algorithm