Covering random points in a unit disk

Jennie C. Hansen; Eric Schmutz; Li Sheng

doi:10.1239/aap/1208358884

Covering random points in a unit disk

Jennie C. Hansen, Eric Schmutz, Li Sheng

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Let D be the punctured unit disk. It is easy to see that no pair x, y in D can cover D in the sense that D cannot be contained in the union of the unit disks centred at x and y. With this fact in mind, let V_n = {X₁, X₂,..., X_n}, where X₁, X₂,.... are random points sampled independently from a uniform distribution on D. We prove that, with asymptotic probability 1, there exist two points in V_n that cover all of V_n. © Applied Probability Trust 2008.

Original language	English
Pages (from-to)	22-30
Number of pages	9
Journal	Advances in Applied Probability
Volume	40
Issue number	1
DOIs	https://doi.org/10.1239/aap/1208358884
Publication status	Published - Mar 2008

Keywords

Dominating set
Random geometric graphy
Unit ball graph

Access to Document

10.1239/aap/1208358884

Cite this

@article{80077ac18de84f1fb5f487c7c56b5bf3,

title = "Covering random points in a unit disk",

abstract = "Let D be the punctured unit disk. It is easy to see that no pair x, y in D can cover D in the sense that D cannot be contained in the union of the unit disks centred at x and y. With this fact in mind, let Vn = {X1, X2,..., Xn}, where X1, X2,.... are random points sampled independently from a uniform distribution on D. We prove that, with asymptotic probability 1, there exist two points in Vn that cover all of Vn. {\textcopyright} Applied Probability Trust 2008.",

keywords = "Dominating set, Random geometric graphy, Unit ball graph",

author = "Hansen, {Jennie C.} and Eric Schmutz and Li Sheng",

year = "2008",

month = mar,

doi = "10.1239/aap/1208358884",

language = "English",

volume = "40",

pages = "22--30",

journal = "Advances in Applied Probability",

issn = "0001-8678",

publisher = "University of Sheffield",

number = "1",

}

TY - JOUR

T1 - Covering random points in a unit disk

AU - Hansen, Jennie C.

AU - Schmutz, Eric

AU - Sheng, Li

PY - 2008/3

Y1 - 2008/3

N2 - Let D be the punctured unit disk. It is easy to see that no pair x, y in D can cover D in the sense that D cannot be contained in the union of the unit disks centred at x and y. With this fact in mind, let Vn = {X1, X2,..., Xn}, where X1, X2,.... are random points sampled independently from a uniform distribution on D. We prove that, with asymptotic probability 1, there exist two points in Vn that cover all of Vn. © Applied Probability Trust 2008.

AB - Let D be the punctured unit disk. It is easy to see that no pair x, y in D can cover D in the sense that D cannot be contained in the union of the unit disks centred at x and y. With this fact in mind, let Vn = {X1, X2,..., Xn}, where X1, X2,.... are random points sampled independently from a uniform distribution on D. We prove that, with asymptotic probability 1, there exist two points in Vn that cover all of Vn. © Applied Probability Trust 2008.

KW - Dominating set

KW - Random geometric graphy

KW - Unit ball graph

UR - http://www.scopus.com/inward/record.url?scp=44649153788&partnerID=8YFLogxK

U2 - 10.1239/aap/1208358884

DO - 10.1239/aap/1208358884

M3 - Article

SN - 0001-8678

VL - 40

SP - 22

EP - 30

JO - Advances in Applied Probability

JF - Advances in Applied Probability

IS - 1

ER -

Covering random points in a unit disk

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this