Central limit theorems for some graphs in computational geometry. (English) Zbl 1044.60016

Penrose, Mathew D.; Yukich, J. E.

Ann. Appl. Probab. 11, No. 4, 1005-1041 (2001).

The purpose of this paper is to establish a general scheme to derive central limit theorems for a great variety of functionals in computational geometry such as the total edge length, the total number of vertices (of certain degree), the total number of edges etc. Among the graphs of interest are the \(k\)-nearest neighbors graph, the sphere of influence graph, the Gabriel graph and the Voronoi and Delaunay tessellations. Let \((B_n)_{n\geq 1}\) be a sequence of bounded Borel sets having volume \(| B_n|= n\) and satisfying some regularity conditions and let \({\mathcal U}_n= \{U^{(n)}_1,\dots, U^{(n)}_n\}\) be a binomial point process and \({\mathcal P}_n\) be a homogeneous Poisson process restricted to \(B_n\). As a main result of this paper under some technical conditions the authors prove that both sequences \(n^{-1/2}(H({\mathcal P}_n)- EH({\mathcal P}_n))\text{ and } n^{-1/2}(H({\mathcal U}_n)- EH({\mathcal U}_n))\) converge weakly to mean zero Gaussian random variables with positive asymptotic variances \(\sigma^2\) and \(\tau^2\), respectively, with \(\sigma^2\geq \tau^2\). Here, \(H(\cdot)\) denotes a translation-invariant functional (defined on finite subsets of \(\mathbb{R}^d\)) satisfying a specific stabilization property.

Reviewer: L. Heinrich (Augsburg)

MSC:

60F05	Central limit and other weak theorems
60D05	Geometric probability and stochastic geometry
60G60	Random fields

Keywords:

Poisson point process; Voronoi tessellation; Delaunay tessellation; proxamity graphs; \(k\)-nearest neighbors graph