Hostname: page-component-cb9f654ff-p5m67 Total loading time: 0 Render date: 2025-08-24T15:58:07.371Z Has data issue: false hasContentIssue false
  • English
  • Français

On the measure of Voronoi cells

Part of: Geometric probability and stochastic geometry

Published online by Cambridge University Press:  22 June 2017

Luc Devroye ,
László Györfi ,
Gábor Lugosi  and
Harro Walk
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.

Keywords

Random pointsetVoronoi tessellationstochastic geometry

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 2 , June 2017 , pp. 394 - 408
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Baccelli, F., Klein, M., Lebourges, M. and Zuyev, S. A. (1997). Stochastic geometry and architecture of communication networks. Telecommun. Systems 7, 209–227. CrossRefGoogle Scholar
[2] Biau, G. and Devroye, L. (2015). Lectures on the Nearest Neighbor Method. Springer, Cham. CrossRefGoogle Scholar
[3] Brakke, K. A. (2005). Statistics of random plane Voronoi tessellations. Unpublished manuscript. Available at http://facstaff.susqu.edu/brakke/aux/downloads/papers/vorplane.pdf. Google Scholar
[4] Brakke, K. A. (2005). Statistics of three dimensional random Voronoi tessellations. Unpublished manuscript. Available at http://facstaff.susqu.edu/brakke/aux/downloads/papers/3d.pdf. Google Scholar
[5] Chiu, S. N., Stoyan, D., Kendall, W. S. and Mecke, J. (2013). Stochastic Geometry and its Applications, 3rd edn. John-Wiley, Chichester. CrossRefGoogle Scholar
[6] Devroye, L. and Györfi, L. (1985). Nonparametric Density Estimation: The L 1 View. John Wiley, New York. Google Scholar
[7] Gilbert, E. N. (1962). Random subdivisions of space into crystals. Ann. Math. Statist. 33, 958–972. CrossRefGoogle Scholar
[8] Hayen, A. and Quine, M. P. (2002). Areas of components of a Voronoi polygon in a homogeneous Poisson process in the plane. Adv. Appl. Prob. 34, 281–291. CrossRefGoogle Scholar
[9] Heinrich, L. and Muche, L. (2008). Second-order properties of the point process of nodes in a stationary Voronoi tessellation. Math. Nachr. 281, 350–375. CrossRefGoogle Scholar
[10] Heinrich, L., Körner, R., Mehlhorn, N. and Muche, L. (1998). Numerical and analytical computation of some second-order characteristics of spatial Poisson–Voronoi tessellations. Statistics 31, 235–259. CrossRefGoogle Scholar
[11] Maier, R., Mayer, J. and Schmidt, V. (2004). Distributional properties of the typical cell of stationary iterated tessellations. Math. Meth. Operat. Res. 59, 287–302. CrossRefGoogle Scholar
[12] Møller, J. (1994). Lectures on Random Voronoi Tessellations (Lecture Notes Statist. 87). Springer, New York. CrossRefGoogle Scholar
[13] Møller, J. and Stoyan, D. (2007). Stochastic geometry and random tessellations. In Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings eds. R. van de Weijgaert et al., Springer, 32pp. Google Scholar
[14] Okabe, A., Boots, B., Sugihara, K. and Chiu, S. N. (2000). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. John Wiley, Chichester. CrossRefGoogle Scholar
[15] Wheeden, R. L. and Zygmund, A. (1977). Measure and Integral. Marcel Dekker, New York. CrossRefGoogle Scholar
[16] Zuyev, S. A. (1992). Estimates for distributions of the Voronoi polygon's geometric characteristics. Random Structures Algorithms 3, 149–162. CrossRefGoogle Scholar