Disc Covering Problem with Application to Digital Halftoning

作     者：Asano, Tetsuo Brass, Peter Sasahara, Shinji 

作者机构：JAIST Sch Informat Sci Tatsunokuchi Ishikawa 9231292 Japan CUNY City Coll Dept Comp Sci New York NY 10031 USA Fuji Xerox Co Ltd Kanagawa 2590157 Japan 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 (计算系统理论)

年 卷 期：2010年第46卷第2期

页      面：157-173页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：Ministry of Education  Science  Sports and Culture 

主　　题：Approximation algorithm Computational geometry Digital halftoning Voronoi diagram 

摘      要：This paper considers the following geometric optimization problem: Input is a matrix R=(r (ij) ). Each entry r (ij) represents a radius of a disc with its center at (i,j) in the plane. We want to choose discs in such a way that the total area covered by exactly one disc is maximized. This problem is closely related to digital halftoning, a technique to convert a continuous-tone image into a binary image for printing. An exact algorithm is given for the one-dimensional version of the problem while approximation algorithms are given for the two-dimensional one. The approximation algorithms are verified to be satisfactory in practice through experiments in applications to digital halftoning.