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:
2009
Usage 100
Abstract Views 59
Full Text Views 28
Downloads 12
Link-outs 1
Captures 6
Readers 5
Exports-Saves 1
Citations 16
Citation Indexes 16
Repository URL:
https://cedar.wwu.edu/math_facpubs/85
DOI:
10.1239/aap/1240319574; 10.1017/s0001867800003116
Author(s):
Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark
Publisher(s):
Cambridge University Press (CUP)
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.