RISC Forum

A family F of subsets of the plane is a k-covering of S if every point of S is covered by at least k sets of F. The covering decomposition problem can be stated as follows: under which conditions can we guarantee that a k-covering can be decomposed into 2 independent coverings, or, more generally, into j independent coverings? Despite some intensive work in the last few years, fundamental questions are still unknown. For instance, no bound for k is known for the basic problem when F is a set of unit disks. In this talk we review some of the results in this area and present the following theorem: If F is a family of congruent copies of a centrally symmetric polygon P, then a k-covering of S can be decomposed into \Omega(\sqrt{k}) independent coverings.

Joint work with Greg Aloupis, Jean Cardinal, Sebastian Colette,
Stefan Langerman, David Orden.