A critical constant for the k nearest-neighbour model
- Citation data:
Advances in Applied Probability, ISSN: 0001-8678, Vol: 41, Issue: 01, Page: 1-12
- Publication Year:
- Repository URL:
- 10.1239/aap/1240319574; 10.1017/s0001867800003116
- Mathematics; Random geometric graph; Connectivity; Poisson process
Let P be a Poisson process of intensity 1 in a square S of area n. For a fixed integer k, join every point of P to its k nearest neighbours, creating an undirected random geometric graph G . We prove that there exists a critical constant c such that, for c < c , G , is disconnected with probability tending to 1 as n → 8 and, for c > c , G , is connected with probability tending to 1 as n → 8. This answers a question posed in Balister et al. (2005). © Applied Probability Trust 2009.