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.
A more sophisticated formalization of the deployment problem allows disks assigned to the same channel to overlap but only counts the area where there is no interference---i.e. the area of the set of points covered by only one disk on some channel. In terms of colouring, the problem is to colour a subset of the given disks to maximize the area of @math for some colour, point @math is in exactly one disk of that colour @math . We call this the . @cite_1 proved that it is always possible to achieve approximately @math 1-covered area using only one colour. This model has also been considered with respect to two other optimization problems. For the problem of maximizing the 1-covered area using one colour, previous work has focused on approximation algorithms (though no proof yet exists, it is suspected that this problem is NP-hard). In @cite_1 , present a 5.83-approximation algorithm with polynomial runtime. In @cite_14 , show that the problem admits a polynomial time approximation scheme when the radius of the largest disk over the radius of the smallest disk is a constant.
@cite_14 @cite_1
2060662766 2099599968
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.