A PTAS for a disc covering problem using width-bounded separators

Author: Chen Zhixiang   Fu Bin   Tang Yong   Zhu Binhai  

Publisher: Springer Publishing Company

ISSN: 1382-6905

Source: Journal of Combinatorial Optimization, Vol.11, Iss.2, 2006-03, pp. : 203-217

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

In this paper, we study the following disc covering problem: Given a set of discs of various radii on the plane and centers on the grid points, 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 (Asano et al., 2004). We show that if their radii are between two positive constants, then there exists a polynomial time approximation scheme. Our techniques are based on the width-bounded geometric separator recently developed in Fu and Wang (2004), Fu (2006).