CENTRAL LIMIT THEOREMS FOR SOME GRAPHS IN COMPUTATIONAL
GEOMETRY
By Mathew D. Penrose and J.E. Yukich
Let (B n) be an increasing sequence of regions in
d-dimensional space with volume n and with union
Rd . We
prove a general central limit theorem for functionals of point
sets, obtained either by restricting a homogeneous Poisson
process to Bn , or by by taking n
uniformly distributed
points in Bn .
The sets Bn could be all cubes but a more
general class of regions Bn is considered.
Using this general result we obtain
central limit theorems for specific functionals such
as total edge length and number of
components, defined in terms of graphs such as the k-nearest neighbors
graph, the sphere of influence graph, and the Voronoi graph.