A critical constant for the k nearest-neighbour model
- 1 March 2009
- journal article
- stochastic geometry-and-statistical-applications
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 41 (01), 1-12
- https://doi.org/10.1017/s0001867800003116
Abstract
Let 𝒫 be a Poisson process of intensity 1 in a square S n of area n. For a fixed integer k, join every point of 𝒫 to its k nearest neighbours, creating an undirected random geometric graph G n,k . We prove that there exists a critical constant c crit such that, for c < c crit, G n,⌊c log n⌋ is disconnected with probability tending to 1 as n → ∞ and, for c > c crit, G n,⌊c log n⌋ is connected with probability tending to 1 as n → ∞. This answers a question posed in Balister et al. (2005).Keywords
This publication has 2 references indexed in Scilit:
- Connectivity of random k-nearest-neighbour graphsAdvances in Applied Probability, 2005
- The Number of Neighbors Needed for Connectivity of Wireless NetworksWireless Networks, 2004