Computing hitting sets for half-planes

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(n7/2log² n) time. In this paper, we present a new algorithm with runtime O(n5/2log² n). For the unweighted case where all points have the same weight, our algorithm runs in O(nlog n) time. This improves the previous best algorithm of O(n³ log n) time by a quadratic factor and matches an Ω(n log n) time lower bound under the algebraic decision tree model.