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:
Usage 103
Abstract Views 61
Full Text Views 28
Downloads 13
Link-outs 1
Captures 6
Readers 5
Exports-Saves 1
Citations 17
Citation Indexes 17
Repository URL:
https://works.bepress.com/amites_sarkar/9; https://cedar.wwu.edu/math_facpubs/85
10.1239/aap/1240319574; 10.1017/s0001867800003116
Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark
Cambridge University Press (CUP)
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.