Improved Approximation Algorithms for Geometric Set Cover

Details Improved Approximation Algorithms for Geometric Set Cover Improved Approximation Algorithms for Geometric Set Cover

2005-01-20

arxiv.org/abs/cs/0501045v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-593444