Minimum-Weight Half-Plane Hitting Set

Abstract

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

To appear in CCCG 2025. arXiv admin note: text overlap with arXiv:2407.00329, arXiv:2501.02195