Algorithms for Halfplane Coverage and Related Problems

Given in the plane a set of points and a set of halfplanes, we consider the problem of computing a smallest subset of halfplanes whose union covers all points. In this paper, we present an \(O(n^{4/3}\log ^{5/3}n\log ^{O(1)}\log n)\) $O(n^{4/3}{log}^{5/3}n{log}^{O(1)}logn)$ -time algorithm for the problem, where n is the total number of all points and halfplanes. This improves the previously best algorithm of \(n^{10/3}2^{O(\log ^*n)}\) $n^{10/3}{2}^{O({log}^{\ast }n)}$ time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in \(O(n\log n)\) $O(nlogn)$ time, which improves the previously best algorithm of \(n^{4/3}2^{O(\log ^*n)}\) $n^{4/3}{2}^{O({log}^{\ast }n)}$ time and matches an \(\Omega (n\log n)\) $\mathrm{\Omega }(nlogn)$ lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in \(O(n\log n)\) $O(nlogn)$ time, which in turn leads to an \(O(n\log n)\) $O(nlogn)$ -time algorithm for computing an instance-optimal \(\varepsilon \) $\epsilon$ -kernel of a set of n points in the plane. Agarwal and Har-Peled presented an \(O(nk\log n)\) $O(nklogn)$ -time algorithm for this problem in SoCG 2023, where k is the size of the \(\varepsilon \) $\epsilon$ -kernel; they also raised an open question whether the problem can be solved in \(O(n\log n)\) $O(nlogn)$ time. Our result thus answers the open question affirmatively.