Given a set P of n weighted points and a set H of n half-planes in the plane, the hitting set problem is to compute a subset P' of points from P such that each half-plane contains at least one point from P' and the total weight of the points in P' is minimized. The previous best algorithm solves the problem in O (n^7/2² n) time. In this paper, we present a new algorithm with runtime O (n^5/2² n). For the unweighted case where all points have the same weight, our algorithm runs in O (n n) time. This improves the previous best algorithm of O (n³ n) time by a quadratic factor and matches an (n n) time lower bound under the algebraic decision tree model.
Liu et al. (Fri,) studied this question.