Decomposing Coverings and the Planar Sensor Cover Problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that a $k$-fold covering using translates of an arbitrary convex polygon can be decomposed into $Ω(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.
18 pages, 13 figures

Keywords

Computational Geometry

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/229660

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0905.1093
 http://arxiv.org/abs/0905.1093

Collections

arXiv