Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T07:27:06.555Z 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.
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the measure of a typical cell in a Voronoi tessellation defined by n independent random points X1, . . ., Xn 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 X1 given X1 = 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
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 2 , June 2017 , pp. 394 - 408
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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