The random disc thrower problem
| Autor: | Aalst, van der, T., Denteneer, T.J.J., Döring, H., Duong, M.H., Kang, R.J., Keane, M.S., Kool, J., Kryven, I., Meyfroyt, T.M.M., Müller, T., Regts, G., Tomczyk, J., Heydenreich, M.O., Hille, S.C., Rottschäfer, V., Spieksma, F., Verbitskiy, E. |
|---|---|
| Přispěvatelé: | Algebra, Geometry & Mathematical Physics (KDV, FNWI), Center for Analysis, Scientific Computing & Appl., Stochastic Operations Research |
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Zdroj: | Proceedings of the 90th European Study Group Mathematics with Industry: SWI 2013: Leiden, 28 Janurary-1 February 2013, 59-78 STARTPAGE=59;ENDPAGE=78;TITLE=Proceedings of the 90th European Study Group Mathematics with Industry: SWI 2013: Leiden, 28 Janurary-1 February 2013 Proceedings of the 90th European Study Group Mathematics in Industry (SWI 2013, Leiden, The Netherlands, January 28-February 1, 2013), 59-78 STARTPAGE=59;ENDPAGE=78;TITLE=Proceedings of the 90th European Study Group Mathematics in Industry (SWI 2013, Leiden, The Netherlands, January 28-February 1, 2013) |
| Popis: | 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 ([6]) that has been the object of close study in both probability theory and statistical physics. Keywords: generating functions, Markov random fields, random sequential adsorption, Rényi’s parking problem, wireless networks |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|