Minimum-Weight Half-Plane Hitting Set

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^{\mathrm{\prime }}$ of points from $P$ such that each half-plane contains at least one point from $P^{\mathrm{\prime }}$ and the total weight of the points in $P^{\mathrm{\prime }}$ is minimized. The previous best algorithm solves the problem in $O(n^{7\mathrm{/}2}{\log }^{2}n)$ time. In this paper, we present a new algorithm with runtime $O(n^{5\mathrm{/}2}{\log }^{2}n)$.