Improved Approximation Algorithms for Geometric Set Cover
| dc.creator | Clarkson, Kenneth L. | |
| dc.creator | Varadarajan, Kasturi | |
| dc.date | 2005-01-20 | |
| dc.date.accessioned | 2026-07-07T03:22:23Z | |
| dc.date.available | 2026-07-07T03:22:23Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0501045 | |
| dc.identifier | http://arxiv.org/abs/cs/0501045 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32572 | |
| dc.subject | Computational Geometry | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2 | |
| dc.title | Improved Approximation Algorithms for Geometric Set Cover | |
| dc.type | text |