Algorithms for Halfplane Coverage and Related Problems
<|reference_start|>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)$-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.<|reference_end|>
@article{wang2024algorithms,
    title={Algorithms for Halfplane Coverage and Related Problems},
    author={Haitao Wang and Jie Xue},
    journal={arXiv preprint arXiv:2402.16323},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16323},
    primaryClass={cs.CG cs.DS}
}