Central Limit Theorems for Some Graphs in Computational Geometry

Let (Bₙ) be an increasing sequence of regions in d -dimensional space with volume n and with union Rᵈ. We prove a general central limit theorem for functionals of point sets, obtained either by restricting a homogeneous Poisson process to (Bₙ), or by by taking n uniformly distributed points in (Bₙ). The sets (Bₙ) could be all cubes but a more general class of regions (Bₙ) 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.