On the variance of the random sphere of influence graph
Paweł Hitczenko, Svante Janson, J. E. Yukich · Random Structures and Algorithms · 1999
We show that the variance of the number of edges in the random sphere of influence graph built on n i.i.d. sites which are uniformly distributed over the unit cube in Rd, grows linearly with n. This is then used to establish a central limit theorem for the number of edges in the random sphere of influence graph built on a Poisson number of sites. Some related proximity graphs are discussed as well. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 139–152, 1999