Helly-type theorems for approximate covering

Let F ∪ {U } be a collection of convex sets in Rd such that F covers U . We prove that if the elements of F and U have comparable size then a small subset of F 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 F , and show that smooth convex sets and axis parallel squares behave differently. We obtain similar results for surface-to-surface visibility amongst balls in 3 dimensions for a notion of volume related to form factor. For each of these situations, we give an algorithm that takes F and U as input and computes in time O (|F | ∗ |Hϵ |) either a point in U not covered by or a subset ϵ covering U up to a measure ϵ, with ϵ meeting our combinatorial bounds.