Computer Science – Computational Geometry
Scientific paper
2005-01-20
Computer Science
Computational Geometry
Scientific paper
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.
Clarkson Kenneth L.
Varadarajan Kasturi
No associations
LandOfFree
Improved Approximation Algorithms for Geometric Set Cover does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Approximation Algorithms for Geometric Set Cover, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Approximation Algorithms for Geometric Set Cover will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-593444