Premium
On the variance of the random sphere of influence graph
Author(s) -
Hitczenko P.,
Janson S.,
Yukich J. E.
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199903)14:2<139::aid-rsa2>3.0.co;2-e
Subject(s) - struct , random graph , unit sphere , central limit theorem , combinatorics , mathematics , random regular graph , graph , poisson distribution , unit cube , variance (accounting) , random geometric graph , cube (algebra) , discrete mathematics , computer science , voltage graph , line graph , statistics , 1 planar graph , accounting , business , programming language
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 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 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