Decomposing Coverings and the Planar Sensor Cover Problem

Simple item page
dc.creatorGibson, Matt
dc.creatorVaradarajan, Kasturi
dc.date2009-05-07
dc.date.accessioned2026-07-07T13:12:43Z
dc.date.available2026-07-07T13:12:43Z
dc.descriptionWe 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.
dc.description18 pages, 13 figures
dc.identifierhttps://arxiv.org/abs/0905.1093
dc.identifierhttp://arxiv.org/abs/0905.1093
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/229660
dc.subjectComputational Geometry
dc.titleDecomposing Coverings and the Planar Sensor Cover Problem
dc.typetext

Files

Collections

arXiv