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 o ur 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 computat ional geometry, our method gives an O(log c) approximation factor. Thi s improves the previous Theta(log\X\) bound of the greedy method and c hallenges recent complexity-theoretic lower bounds for set covers (whi ch do not make any assumptions about the VC-dimension). We give severa l applications of our method to computational geometry, and we show th at 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.