Helly-type theorems for approximate covering

Let ℱ ∪ {U} be a collection of convex sets in Double strok R sign^d such that ℱ covers U. We show that if the elements of ℱ and U have comparable size, in the sense that each contains a ball of radius γ and is contained in a ball of radius R for some fixed γ and R, then for any ε > 0 there exists Hε, ⊂, whose size H _ε is polynomial in 1/ε and independent of ℱ, 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 ℱ; specifically, we prove that it is O(_ε¹) when ℱ consists of axis-parallel unit squares in the plane and Õ(ε^1-d/2) when ℱ consists of unit balls in Doule strok R sign^d (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. We extend these results to surface-to-surface visibility in 3 dimensions: if a collection ℱ of disjoint unit balls occludes visibility between two balls then a subset of ℱ of size Õ(ε^-7/2) blocks visibility along all but a set of lines of measure ε. Finally, for each of the above situations we give an algorithm that takes ℱ and U as input and outputs in time (ℱ *H_ε ) either a point in U not covered by ℱ or a subset H_epsi; covering U up to a measure ε, with H_ε satisfying the above bounds.