On Line-Separable Weighted Unit-Disk Coverage and Related Problems

Given a set P of n points and a set S of n weighted disks in the plane, the disk coverage problem is to compute a subset of disks of smallest total weight such that the union of the disks in the subset covers all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line. We present an O (n^3/2² n) time algorithm for the problem. This improves the previously best work of O (n² n) time. Our result leads to an algorithm of O (n^{7/2}² n) time for the halfplane coverage problem (i. e. , using n weighted halfplanes to cover n points), an improvement over the previous O (n⁴ n) time solution. If all halfplanes are lower ones, our algorithm runs in O (n^{3/2}² n) time, while the previous best algorithm takes O (n² n) time. Using duality, the hitting set problems under the same settings can be solved with similar time complexities.