Improved Approximation Algorithms for Geometric Set Cover
<|reference_start|>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 a subset of 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 usually U = R^d. Extending prior results, we show that approximation algorithms with provable performance exist, under a certain general condition: that for a random subset R of S and function f(), there is a decomposition of the portion of U not covered by R into an expected f(|R|) regions, each region of a particular simple form. We show that under this condition, 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 R^3, for guarding a one-dimensional terrain, and for covering by similar-sized fat triangles in R^2. We also obtain improved approximation guarantees for fat triangles, of arbitrary size, and for a class of fat objects.<|reference_end|>
@article{clarkson2005improved,
    title={Improved Approximation Algorithms for Geometric Set Cover},
    author={Kenneth L. Clarkson and Kasturi Varadarajan},
    journal={arXiv preprint arXiv:cs/0501045},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0501045},
    primaryClass={cs.CG cs.DS}
}