Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/53645
Type: Artigo de periódico
Title: A PTAS for the disk cover problem of geometric objects
Author: de Rezende, PJ
Miyazawa, FK
Sasaki, AT
Abstract: We present PTASs for the disk cover problem: given geometric objects and a finite set of disk centers, minimize the total cost for covering those objects with disks under a polynomial cost function on the disks' radii. We describe the first FPTAS for covering a line segment when the disk centers form a discrete set, and a PTAS for when a set of geometric objects, described by polynomial algebraic inequalities, must be covered. The latter result holds for any dimension. (C) 2013 Elsevier B.V. All rights reserved.
Subject: Disk cover
Approximation algorithm
Computational geometry
Wireless networks
Sensor coverage
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.orl.2013.06.014
Date Issue: 2013
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.