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