Philips – The Random Disc Thrower Problem #SWI2013

Philips Research is a global organization that helps Philips introduce meaningful innovations that improve people’s lives. We provide
technology options in the area of health and well-being for both developed and emerging markets. Positioned at the front-end of the
innovation process, we work on everything from spotting trends and ideation to proof of concept and – where needed – first-of-a-kind
product development.

We consider a grid of point in a rectangular area. A disc thrower throws discs of the fixed radius on the area so that each disc is centered on a grid point that is randomly and uniformly chosen from the grid points that are not yet covered by one of the discs. Disc radiuses are greater than the distances between two neighboring grid points. Hence one disc can cover several grid points, moreover, discs are allowed to intersect. The disc thrower continues throwing his discs until the whole area is covered. The question is, how many discs does the disc thrower need to complete this random covering on average, or, more challenging, what is the distribution of the number of discs needed.
This problem, and its more complex variants (also to be presented at the workgroup), touch upon fundamental problems of spatial reuse in a wireless network. They, e.g., relate to the performance of distributed, stochastic gossiping algorithms, as used for maintenance and update of network information. As such, the questions apply to e.g. beaconing in IEEE 802.11 mesh networks, and code propagation in sensor networks.