Article
A Critical Constant for the k Nearest-Neighbour Model
Advances in Applied Probability
Document Type
Article
Publication Date
1-1-2009
Keywords
- Random geometric graph,
- Connectivity,
- Poisson process
Disciplines
Abstract
Let P be a Poisson process of intensity 1 in a square Sn of area n. For a fixed integer k, join every point of P to its k nearest neighbours, creating an undirected random geometric graph Gn,k. We prove that there exists a critical constant ccrit such that, for c‹ccrit, Gn,⌊clogn⌋ is disconnected with probability tending to 1 as n →∞ and, for c‹ccrit, Gn,⌊clogn⌋ is connected with probability tending to 1 as n →∞. This answers a question posed in Balister et al. (2005).
DOI
http://dx.doi.org/10.1239/aap/1240319574
Comments
This is the authors' version of the article. The publisher version is at: http://projecteuclid.org/euclid.aap/1240319574
Subjects - Topical (LCSH)
Random graphs; Graph connectivity; Poisson processes
Genre/Form
articles
Type
Text
Rights
Copying of this document in whole or in part is allowable only for scholarly purposes. It is understood, however, that any copying or publication of this document for commercial purposes, or for financial gain, shall not be allowed without the author’s written permission.
Language
English
Format
application/pdf
Citation Information
Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. A critical constant for the k nearest-neighbour model. Adv. in Appl. Probab. 41 (2009), no. 1, 001--012. doi:10.1239/aap/1240319574. http://projecteuclid.org/euclid.aap/1240319574.
This is the authors' version of the article. The publisher version is at: http://projecteuclid.org/euclid.aap/1240319574