The random disc thrower problem

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 network