Random geometric graph, Connectivity, Poisson process
Let � be a Poisson process of intensity 1 in a square Sn of area n. For a fixed integer k, join every point of � to its k nearest neighbours, creating an undirected random geometric graph Gn,k. We prove that there exists a critical constant ccrit such that, for c‹ccrit, Gn,⌊clogn⌋ is disconnected with probability tending to 1 as n →∞ and, for c‹ccrit, Gn,⌊clogn⌋ is connected with probability tending to 1 as n →∞. This answers a question posed in Balister et al. (2005).
Advances in Applied Probability
Required Publisher's Statement
Published by Project Euclid
Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. A critical constant for the k nearest-neighbour model. Adv. in Appl. Probab. 41 (2009), no. 1, 001--012. doi:10.1239/aap/1240319574. http://projecteuclid.org/euclid.aap/1240319574.