Covering Random Points in a Unit Ball
Jennie C. Hansen, Eric Schmutz · 2006
Choose random pointsX1, X2, X3, . . . independently from a uniform distribution in a unit ball in <. Call Xn a dominator iff distance(Xn, Xi) ≤ 1 for all i < n, i.e. the first n points are all contained in the unit ball that is centered at the n’th point Xn. We prove that, with probability one, only finitely many of the points are dominators. For the special casem = 2, we consider the unit disk graph Gn determined by n random points X1, X2, . . . , Xn in the unit disk. With asymptotic probability one, Gn has a connected dominating set consisting of just two points. keywords and phrases: stochastic geometry, dominating set, geometric graph, unit ball graph