Computer Science – Computational Geometry
Scientific paper
2009-05-07
Computer Science
Computational Geometry
18 pages, 13 figures
Scientific paper
We show that a $k$-fold covering using translates of an arbitrary convex polygon can be decomposed into $\Omega(k)$ covers (using an efficient algorithm). We generalize this result to obtain a constant factor approximation to the sensor cover problem where the ranges of the sensors are translates of a given convex polygon. The crucial ingredient in this generalization is a constant factor approximation algorithm for a one-dimensional version of the sensor cover problem, called the Restricted Strip Cover (RSC) problem, where sensors are intervals of possibly different lengths. Our algorithm for RSC improves on the previous $O(\log \log \log n)$ approximation.
Gibson Matt
Varadarajan Kasturi
No associations
LandOfFree
Decomposing Coverings and the Planar Sensor Cover Problem 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 Decomposing Coverings and the Planar Sensor Cover Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decomposing Coverings and the Planar Sensor Cover Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-456110