Coverings: Variations on a result of Rogers and on the Epsilon-net theorem of Haussler and Welzl

We consider four problems. Rogers proved that for any convex body $K$, we can cover ${\mathbb{R}}^d$ by translates of $K$ of density very roughly $dlnd$. First, we extend this result by showing that, if we are given a family of positive homothets of $K$ of infinite total volume, then we can find appropriate translation vectors for each given homothet to cover ${\mathbb{R}}^d$ with the same (or, in certain cases, smaller) density.Second, we extend Rogers’ result to multiple coverings of space by translates of a convex body: we give a non-trivial upper bound on the density of the most economical covering where each point is covered by at least a certain number of translates.Third, we show that for any sufficiently large $n$, the sphere ${\mathbb{S}}^2$ can be covered by $n$ strips of width $20n∕lnn$, where no point is covered too many times.Finally, we give another proof of the previous result based on a combinatorial observation: an extension of the Epsilon-net Theorem of Haussler and Welzl. We show that for a hypergraph of bounded Vapnik–Chervonenkis dimension, in which each edge is of a certain measure, there is a not-too large transversal set which does not intersect any edge too many times.