Improved Approximation Algorithms for Geometric Set Cover

Computer Science – Computational Geometry

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-593444

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.