#
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
*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 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.