Skip to main content
Article
A Critical Constant for the k Nearest-Neighbour Model
Advances in Applied Probability
  • Paul Balister, University of Memphis
  • Béla Bollobás, University of Memphis
  • Amites Sarkar, Western Washington University
  • Mark Walters, Trinity College
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 cccrit, Gn,⌊clogn⌋ is disconnected with probability tending to 1 as n →∞ and, for cccrit, 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
Required Publisher's Statement

This is the authors' version of the article. The publisher version is at: http://projecteuclid.org/euclid.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.