An Optimal Algorithm for Half-plane Hitting Set

Abstract

Given a set $P$ of $n$ points and a set $H$ of $n$ half-planes in the plane, we consider the problem of computing a smallest subset of points such that each half-plane contains at least one point of the subset. The previously best algorithm solves the problem in $O(n^3\log n)$ time. It is also known that $\hat{I}\text{c◯}(n\log n)$ is a lower bound for the problem under the algebraic decision tree model. In this paper, we present an $O(n\log n)$ time algorithm, which matches the lower bound and thus is optimal. Another virtue of the algorithm is that it is relatively simple.

To appear in SOSA 2025