On the Line-Separable Unit-Disk Coverage and Related Problems
share
Given a set P of n points and a set S of m disks in the plane, the disk coverage problem asks for a smallest subset of disks that together cover 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 m^2/3n^2/32^O(log^*(m+n)) + O((n+m)log (n+m)) time algorithm for the problem. This improves the previously best result of O(nm+ nlog n) time. Our techniques also solve the line-constrained version of the problem, where centers of all disks of S are located on a line ℓ while points of P can be anywhere in the plane. Our algorithm runs in O(m√(n) + (n+m)log(n+m)) time, which improves the previously best result of O(nmlog(m+n)) time. In addition, our results lead to an algorithm of n^10/32^O(log^*n) time for a half-plane coverage problem (given n half-planes and n points, find a smallest subset of half-planes covering all points); this improves the previously best algorithm of O(n^4log n) time. Further, if all half-planes are lower ones, our algorithm runs in n^4/32^O(log^*n) time while the previously best algorithm takes O(n^2log n) time.
READ FULL TEXT