A PTAS for a Disc Covering Problem Using Width-Bounded Separators

摘要：

In this paper, we study the following disc covering problem: Given a set of discs of various radii on the plane, find a subset of discs to maximize the area covered by exactly one disc. This problem originates from the application in digital halftoning, with the best known approximation factor being 5.83 2. We show that if the maximum radius is no more than a constant times the minimum radius, then there exists a polynomial time approximation scheme. Our techniques are based on the width-bounded geometric separator recently developed in 5, 6.

作者: Zhixiang Chen Bin Fu Yong Tang Binhai Zhu

作者单位: Dept. of Computer Science,University of Texas -Pan American, TX 78539, USA Dept. of Computer Science, University of New Orleans, LA 70148, USA Research Institute for Children, Dept. of Computer Science, Sun Yat-Sen University, Guangzhou 510275, China Dept. of Computer Science, Montana State University, MT 59717-3880, USA

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 490-503

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）