On the variance of the random sphere of influence graph

Authors
Hitczenko, P Janson, S Yukich, JE
Citation
P. Hitczenko et al., On the variance of the random sphere of influence graph, RAND STR AL, 14(2), 1999, pp. 139-152
Citations number
16
Categorie Soggetti
Mathematics
Journal title
RANDOM STRUCTURES & ALGORITHMS
ISSN journal
10429832 → ACNP
Volume
14
Issue
2
Year of publication
1999
Pages
139 - 152
Database
ISI
SICI code
1042-9832(199903)14:2<139:OTVOTR>2.0.ZU;2-R
Abstract
We show that the variance of the number of edges in the random sphere of in fluence graph built on n i.i.d. sites which are uniformly distributed over the unit cube in R-d, grows linearly with n. This is then used to establish a central limit theorem for the number of edges in the random sphere of in fluence graph built on a Poisson number of sites. Some related proximity gr aphs are discussed as well. (C) 1999 John Wiley & Sons, Inc.