On the measure of Voronoi cells. (22nd June 2017)

• Record Type: Journal Article
• Authors: Devroye, Luc; Györfi, László; Lugosi, Gábor; Walk, Harro
• Is Part Of: Journal of applied probability. Volume 54:Number 2(2017)
• Page Start: 394
• Page End: 408
• Publication Date: 2017-06-22
• Subjects: Random pointset, -- Voronoi tessellation, -- stochastic geometry; Primary 60D05; 519.2
• DOI: 10.1017/jpr.2017.7
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract: We study the measure of a typical cell in a Voronoi tessellation defined by n independent random points X 1, . . ., X n drawn from an absolutely continuous probability measure μ with density f in ℝ d . We prove that the asymptotic distribution of the measure – with respect to dμ = f ( x )d x – of the cell containing X 1 given X 1 = x is independent of x and the density f . We determine all moments of the asymptotic distribution and show that the distribution becomes more concentrated as d becomes large. In particular, we show that the variance converges to 0 exponentially fast in d . We also obtain a bound independent of the density for the rate of convergence of the diameter of a typical Voronoi cell.