A Caltech Library Service

Covering algorithms, continuum percolation and the geometry of wireless networks

Booth, Lorna and Bruck, Jehoshua and Franceschetti, Massimo and Meester, Ronald (2003) Covering algorithms, continuum percolation and the geometry of wireless networks. Annals of Applied Probability, 13 (2). pp. 722-741. ISSN 1050-5164. doi:10.1214/aoap/1050689601.

See Usage Policy.


Use this Persistent URL to link to this item:


Continuum percolation models in which each point of a two-dimensional Poisson point process is the centre of a disc of given (or random) radius r, have been extensively studied. In this paper, we consider the generalization in which a deterministic algorithm (given the points of the point process) places the discs on the plane, in such a way that each disc covers at least one point of the point process and that each point is covered by at least one disc. This gives a model for wireless communication networks, which was the original motivation to study this class of problems. We look at the percolation properties of this generalized model, showing that an unbounded connected component of discs does not exist, almost surely, for small values of the density lambda of the Poisson point process, for any covering algorithm. In general, it turns out not to be true that unbounded connected components arise when lambda is taken sufficiently high. However, we identify some large families of covering algorithms, for which such an unbounded component does arise for large values of lambda. We show how a simple scaling operation can change the percolation properties of the model, leading to the almost sure existence of an unbounded connected component for large values of lambda, for any covering algorithm. Finally, we show that a large class of covering algorithms, which arise in many practical applications, can get arbitrarily close to achieving a minimal density of covering discs. We also construct an algorithm that achieves this minimal density.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2006 The Institute of Mathematical Statistics. Received May 2001; revised April 2002. The authors thank Richard Gill. We also thank Johan Segers for reading an early version of this article very carefully and for the many interesting comments and observations that resulted. Massimo Franceschetti thanks his fellow student Matthew Cook for many interesting discussions and for reading and providing feedback on some of the proofs. We also thank the referee for scrutinizing the paper scrupulously and suggesting some improved proofs.
Subject Keywords:Covering algorithms; (continuum) percolation; wireless communication networks; phase transition
Issue or Number:2
Record Number:CaltechAUTHORS:BOOaoap03
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3882
Deposited By: Lindsay Cleary
Deposited On:18 Jul 2006
Last Modified:08 Nov 2021 20:13

Repository Staff Only: item control page