ALMOST OPTIMAL SET COVERS IN FINITE VC-DIMENSION

We give a deterministic polynomial-rime method for finding a set cover in a set system (X, R) of dual VC-dimension d such that the size of our cover is at most a factor of O(d log(dc)) from the optimal size, c. For constant VC-dimensional set systems, which are common in computational geometry, our method gives an O(log c) approximation factor. This improves the previous Theta(log\X\) bound of the greedy method and challenges recent complexity-theoretic lower bounds for set covers (which do not make any assumptions about the VC-dimension). We give several applications of our method to computational geometry, and we show that in some cases, such as those arising in three-dimensional polytope approximation and two-dimensional disk covering, we can quickly find O(c)-sized covers.