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.
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).
Related content
A robust sensor covering and communication problem
Naval Research Logistics: An International Journal, Vol. 62, Iss. 7, 2015-10 ,pp. :
A multicriteria problem of distribution of bounded resources
By Voronin A.
Cybernetics and Systems Analysis, Vol. 47, Iss. 3, 2011-05 ,pp. :
On the uniqueness of a bounded solution of the radiation transport problem
By Muradyan M.
Differential Equations, Vol. 43, Iss. 5, 2007-05 ,pp. :
The Bounded Degree Problem for eNCE Graph Grammars
Information and Computation, Vol. 135, Iss. 1, 1997-05 ,pp. :