Helly-type theorems for approximate covering
Julien Demouth, Olivier Devillers, Marc Glisse, Xavier Goaoc · 2008
Let F ∪ {U} be a collection of convex sets in Rd such that F covers U. We show that if the elements of F and U have comparable size, in the sense that each contains a ball of radius r and is contained in a ball of radius R for some fixed r and R, then for any ε > 0 there exists Hε ⊂ F, whose size |Hε| is polynomial in 1/ε and independent of |F|, that covers U except for a volume of at most ε. The size of the smallest such subset depends on the geometry of the elements of F; specifically, we prove that it is O(1/ε) when F consists of axis-parallel unit squares in the plane and Õ(ε1--d/2) when F consists of unit balls in Rd (here, Õ(n) means O(n log n) for some constant), and that these bounds are, in the worst-case, tight up to the logarithmic factors.