Given a set of unit-disks in the plane with union area @math , what fraction of @math can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1 4 and proved @math . Motivated by the problem of channel-assignment for wireless access points, in which use of 3 channels is a standard practice, we consider a variant where the selected subset of disks must be 3-colourable with disks of the same colour pairwise-disjoint. For this variant of the problem, we conjecture that it is always possible to cover at least @math of the union area and prove @math . We also provide an @math algorithm to select a subset achieving a @math bound.
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. Thisproblem originates from the application in digital halftoning, with the best known approximation factor being 5.83 (, 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). 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.