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.