A PTAS for the disk cover problem of geometric objects

详细信息    查看全文

• 作者：Pedro J. de Rezende ; Fl¨¢vio K. Miyazawa ; Anderson T. Sasaki
• 关键词：Disk cover ; Approximation algorithm ; Computational geometry ; Wireless networks ; Sensor coverage
• 刊名：Operations Research Letters
• 出版年：2013
• 出版时间：September, 2013
• 年：2013
• 卷：41
• 期：5
• 页码：552-555
• 全文大小：359 K

文摘

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.