Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-27T19:58:38.932Z Has data issue: false hasContentIssue false
  • English
  • Français

Covering random points in a unit disk

Part of: Geometric probability and stochastic geometry Discrete mathematics in relation to computer science

Published online by Cambridge University Press:  01 July 2016

Jennie C. Hansen ,
Eric Schmutz  and
Li Sheng
Jennie C. Hansen*
Affiliation:
Herriot-Watt University
Eric Schmutz*
Affiliation:
Drexel University
Li Sheng*
Affiliation:
Drexel University
*
∗ Postal address: Actuarial Mathematics and Statistics Department and the Maxwell Institute for Mathematical Sciences, Herriot-Watt University, Riccarton, Edinburgh EH14 4AS, UK.
∗∗ Postal address: Mathematics Department, Drexel University, Philadelphia, PA 19104, USA.
∗∗ Postal address: Mathematics Department, Drexel University, Philadelphia, PA 19104, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

Dominating setrandom geometric graphunit ball graph

MSC classification

Primary: 60D05: Geometric probability and stochastic geometry
Secondary: 68R10: Graph theory (including graph drawing)
Type
Stochastic Geometry and Statistical Applications
Information
Advances in Applied Probability , Volume 40 , Issue 1 , March 2008 , pp. 22 - 30
Copyright
Copyright © Applied Probability Trust 2008 

References

Clark, B. N., Colburn, C. J. and Johnson, D. J. (1990). Unit disk graphs. Discrete Math. 86, 165–177.Google Scholar
Dai, F. and Wu, J. (2004). An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distributed Systems 15, 908–920.Google Scholar
Gupta, P. and Kumar, P. R. (2000). The capacity of wireless networks. IEEE Trans. Inf. Theory 46, 388–404.CrossRefGoogle Scholar
Gupta, P. and Kumar, P. R. (2001). Internets in the sky: the capacity of three dimensional wireless networks. Commun. Inf. Systems 1, 33–49.Google Scholar
Hall, P. (1998). Introduction to the Theory of Coverage Processes. John Wiley, New York.Google Scholar
Hansen, J. C. and Schmutz, E. (2005). Comparison of two CDS algorithms on random unit ball graphs. In Proc. 7th Workshop Algorithm Eng. Experiments/2nd Workshop Analytic Algorithms Combin., Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 208–213.Google Scholar
Hansen, J. C., Schmutz, E. and Sheng, L. (2006). The expected size of the rule k dominating set. Algorithmica 46, 409–418.CrossRefGoogle Scholar
Jacquet, P. A., Laouiti, P. A., Minet, P. and Viennot, L. (2002). Performance of multipoint relaying in ad hoc mobile routing protocols. In Networking 2002 (Lecture Notes Comput. Sci. 2345), Springer, Berlin, pp. 387–398.Google Scholar
Wu, J. and Li, H. (1999). On calculating connected dominating set for efficient routing in ad hoc wireless networks. In Workshop on Discrete Algorithms and Methods for MOBILE Computing and Communications, ACM, New York, pp. 7–14.Google Scholar