Improved Approximation Algorithms for Geometric Set Cover

Given a collection S of subsets of some set U, and M a subset of U, the *set cover* problem is to find the smallest subcollection C of S such that M is contained in the union of the sets in C. While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where ususally U = R^d. Extending prior results, we give a general condition implying the existence of approximation algorithms. We show that if there is a decomposition of the complement of the union of the sets in T into an expected f(|T|) simple regions, for a function f() and T a random subset of S, then a cover of size O(f(|C|)) can be found. Our proof involves the generalization of *shallow cuttings* to more general geometric situations. We obtain constant-factor approximation algorithms for covering by unit cubes in R3, for guarding a one-dimensional terrain, and for covering by similar-sized fat triangles in R3. We also obtain improved approximation guarantees for fat triangles, of arbitrary size, and for a class of fat objects.