Central Limit Theorems for Some Graphs in Computational Geometry

Abstract

Let $(B_n)$ be an increasing sequence of regions in $d$ -dimensional space with volume $n$ and with union $\mathbb{R}^d$. We prove a general central limit theorem for functionals of point sets, obtained either by restricting a homogeneous Poisson process to $(B_n)$, or by by taking $n$ uniformly distributed points in $(B_n)$. The sets $(B_n)$ could be all cubes but a more general class of regions$(B_n)$ is considered. Using this general result we obtain central limit theorems for specific functionals suchas total edge lengthand number of components, defined in terms of graphs such as the $k$-nearest neighbors graph, the sphere of influence graph and the Voronoi graph.