A critical constant for the k nearestneighbour model
 Citation data:

Advances in Applied Probability, ISSN: 00018678, Vol: 41, Issue: 01, Page: 112
 Publication Year:
 2009
 Repository URL:
 https://cedar.wwu.edu/math_facpubs/85
 DOI:
 10.1239/aap/1240319574; 10.1017/s0001867800003116
 Author(s):
 Publisher(s):
 Tags:
 Mathematics; Random geometric graph; Connectivity; Poisson process
article description
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.