Conference proceeding
Decomposing Coverings and the Planar Sensor Cover Problem
2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp.159-168
10/2009
DOI: 10.1109/FOCS.2009.54
Abstract
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.
Details
- Title: Subtitle
- Decomposing Coverings and the Planar Sensor Cover Problem
- Creators
- M Gibson - University of IowaK Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pp.159-168
- Publisher
- IEEE
- DOI
- 10.1109/FOCS.2009.54
- ISSN
- 0272-5428
- Language
- English
- Date published
- 10/2009
- Academic Unit
- Computer Science
- Record Identifier
- 9984259475402771
Metrics
11 Record Views