Key points are not available for this paper at this time.
Given a set P of n points and a set S of m disks in the plane, the disk hitting set problem asks for a smallest subset of P such that every disk of S contains at least one point in the subset. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks have their centers on a line. We present an O (m²n+ (n+m) (n+m) ) time algorithm for the problem. This improves the previously best result of O (m² m+ (n+m) (n+m) ) time for the weighted case of the problem where every point of P has a weight and the objective is to minimize the total weight of the hitting set. Our algorithm actually solves a more general line-separable problem with a single intersection property: The points of P and the disk centers are separated by a line and the boundary of every two disks intersect at most once on the side of containing P.
Liu et al. (Sat,) studied this question.