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^5/3n^O (1) n) -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/32^O (^*n) time by roughly a quadratic factor. For the special case where all halfplanes are lower ones, our algorithm runs in O (n n) time, which improves the previously best algorithm of n^4/32^O (^*n) time and matches an (n n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O (n n) time, which in turn leads to an O (n n) -time algorithm for computing an instance-optimal -kernel of a set of n points in the plane. Agarwal and Har-Peled presented an O (nk n) -time algorithm for this problem in SoCG 2023, where k is the size of the -kernel; they also raised an open question whether the problem can be solved in O (n n) time. Our result thus answers the open question affirmatively.