T. van der Aalst
- The random disc thrower problem
- 90th European Study Group Mathematics with Industry, SWI 2013
- Book/source title
- Proceedings of the 90th European Study Group Mathematics with Industry: SWI 2013: Leiden, 28 Janurary - 1 February 2013
- Pages (from-to)
- Leiden: Universiteit Leiden, Studiegroep Wiskunde met de Industrie
- Document type
- Conference contribution
- Faculty of Science (FNWI)
- Korteweg-de Vries Institute for Mathematics (KdVI)
We describe a number of approaches to a question posed by Philips Research, described as the "random disc thrower" problem. Given a square grid of points in the plane, we cover the points by equal-sized planar discs according to the following random process. At each step, a random point of the grid is chosen from the set of uncovered points as the centre of a new disc. This is an abstract
model of spatial reuse in wireless networks. A question of Philips Research asks what, as a function of the grid length, is the expected number of discs chosen before the process can no longer continue? Our main results concern the one-dimensional variant of this problem, which can be solved reasonably well, though we also provide a number of approaches towards an approximate solution of the original two-dimensional problem. The two-dimensional problem is related to an old, unresolved conjecture () that has been the object of close study in both probability theory and statistical physics.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.