Helly-Type Theorems for Approximate Covering

Let ℱ∪{U} be a collection of convex sets in ℝ ^d such that ℱ covers U. We prove that if the elements of ℱ and U have comparable size, then a small subset of ℱ suffices to cover most of the volume of U; we analyze how small this subset can be depending on the geometry of the elements of ℱ and show that smooth convex sets and axis parallel squares behave differently. We obtain similar results for surface-to-surface visibility amongst balls in three dimensions for a notion of volume related to form factor. For each of these situations, we give an algorithm that takes ℱ and U as input and computes in time O(|ℱ|*|ℋ _ε |) either a point in U not covered by ℱ or a subset ℋ _ε covering U up to a measure ε, with |ℋ _ε | meeting our combinatorial bounds. The authors acknowledge support from the French–Korean Science and Technology amicable relationship program (STAR) 11844QJ.