Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-19T01:14:16.459Z Has data issue: false hasContentIssue false

On the measure of Voronoi cells

Published online by Cambridge University Press:  22 June 2017

Luc Devroye*
Affiliation:
McGill University
László Györfi*
Affiliation:
Budapest University of Technology and Economics
Gábor Lugosi*
Affiliation:
ICREA and Pompeu Fabra University
Harro Walk*
Affiliation:
Universität Stuttgart
*
* Postal address: School of Computer Science, McGill University, 3480 University Street, Montreal, H3A 0E9, Canada.
** Postal address: Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar Tudósok krt. 2., Budapest, H-1117, Hungary.
*** Postal address: Department of Economics and Business, Pompeu Fabra University, Ramon Trias Fargas 25-27, 08005 Barcelona, Spain.
**** Postal address: Institut für Stochastik und Anwendungen, Universität Stuttgart, Pfaffenwaldring 57, D-70569 Stuttgart, Germany.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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)dx – 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.

Information

Type
Research Papers
Copyright
Copyright © Applied Probability Trust 2017