Decomposing Coverings and the Planar Sensor Cover Problem

Details Decomposing Coverings and the Planar Sensor Cover Problem Decomposing Coverings and the Planar Sensor Cover Problem

2009-05-07

arxiv.org/abs/0905.1093v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-456110