Covering algorithms, continuum percolation and the geometry of wireless networks (Q1413688)

Given the points of a planar point process, the authors consider an algorithm that places discs on the plane in such a way that each disc covers at least one point of the point process and that each point is covered by at least one disc. The model was motivated by applications to wireless communication networks. A particular case of this model corresponds to the continuum percolation setting where discs are centred at the points of the point process. The authors study the percolation properties of this model and show that an unbounded connected component of discs does not exist, almost surely, for small values of the intensity \(\lambda\) of the Poisson point process, for any covering algorithm. In general, it turns out not to be true that unbounded connected components arise when \(\lambda\) is taken sufficiently high. However, the authors identify some large families of covering algorithms, for which an unbounded component does arise for large values of \(\lambda\). It is shown how a simple scaling operation changes the percolation properties of the model, so that an unbounded connected component exists for large \(\lambda\) and any covering algorithm. It is also shown that a large class of important covering algorithms can get arbitrarily close to achieving a minimal density of covering discs. The authors construct an algorithm that achieves this minimal density.