Covering Decomposition and Geometric Hypergraph Coloring
Given a k-fold covering of the plane by translates of a convex body, in how many 1-fold coverings can we decompose it, as a function of k? This problem was formulated in the early eighties in the discrete geometry community, and still does not have a complete solution. We will survey recent results of ours on this and several related variants. Along the way, we will discuss connections to epsilon-nets and approximation algorithms for covering and coloring problems in hypergraphs.