Geometric Hitting Set for Line-Constrained Disks and Related Problems
share
Given a set P of n weighted points and a set S of m disks in the plane, the hitting set problem is to compute a subset P' of points of P such that each disk contains at least one point of P' and the total weight of all points of P' is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line ℓ. 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. 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 the problem in O((m + n)log(m + n)) time in the L_∞ and L_1 metrics, in which a disk is a square and a diamond, respectively. Our techniques can also be used to solve other geometric hitting set problems. For example, given in the plane a set P of n weighted points and a set S of n half-planes, we solve in O(n^4log n) time the problem of finding a minimum weight hitting set of P for S. This improves the previous best algorithm of O(n^6) time by nearly a quadratic factor.
READ FULL TEXT