Algorithms for the Line-Constrained Disk Coverage and Related Problems
share
Given a set P of n points and a set S of m weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of P. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line L (while points of P can be anywhere in the plane). We present an O((m+n)log(m+n)+κlog m) time algorithm for the problem, where κ is the number of pairs of disks that intersect. Alternatively, we can also solve the problem in O(nmlog(m+n)) time. For the unit-disk case where all disks have the same radius, the running time can be reduced to O((n+m)log(m+n)). In addition, we solve in O((m+n)log(m+n)) time the L_∞ and L_1 cases of the problem, in which the disks are squares and diamonds, respectively. As a by-product, the 1D version of the problem where all points of P are on L and the disks are line segments on L is also solved in O((m+n)log(m+n)) time. We also show that the problem has an Ω((m+n)log (m+n)) time lower bound even for the 1D case. We further demonstrate that our techniques can also be used to solve other geometric coverage problems. For example, given in the plane a set P of n points and a set S of n weighted half-planes, we solve in O(n^4log n) time the problem of finding a subset of half-planes to cover P so that their total weight is minimized. This improves the previous best algorithm of O(n^5) time by almost a linear factor. If all half-planes are lower ones, then our algorithm runs in O(n^2log n) time, which improves the previous best algorithm of O(n^4) time by almost a quadratic factor.
READ FULL TEXT