Central limit theorems for some graphs in computational geometry. (Q1872436): Difference between revisions

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.