Document Type
Article
Publication Date
2010
Keywords
Poisson process, coverage, partition
Abstract
Let P be a Poisson process of intensity one in the infinite plane R2. We surround each point x of P by the open disc of radius r centred at x. Now let Sn be a fixed disc of area n, and let Cr(Sn) be the set of discs which intersect Sn. Write Erk for the event that Cr(Sn) is a k-cover of Sn, and Frk for the event that Cr(Sn) may be partitioned into k disjoint single covers of Sn. We prove that P(Erk ∖ Frk) ≤ ck / logn, and that this result is best possible. We also give improved estimates for P(Erk). Finally, we study the obstructions to k-partitionability in more detail. As part of this study, we prove a classification theorem for (deterministic) covers of R2 with half-planes that cannot be partitioned into two single covers.
Publication Title
Advances in Applied Probability
Volume
42
Issue
1
First Page
1
Last Page
25
DOI
http://dx.doi.org/10.1239/aap/1269611141
Required Publisher's Statement
Published by Project Euclid
DOI: 10.1239/aap/1269611141
Recommended Citation
Balister, Paul; Bollobás, Béla; Sarkar, Amites; Walters, Mark. Sentry selection in wireless networks. Adv. in Appl. Probab. 42 (2010), no. 1, 1--25. doi:10.1239/aap/1269611141. http://projecteuclid.org/euclid.aap/1269611141.
Subjects - Topical (LCSH)
Poisson processes; Partitions (Mathematics); Wireless sensor networks--Mathematical models
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
Comments
This is the authors' version of the paper. The publisher's version is here: http://projecteuclid.org/euclid.aap/1269611141