2026-07-21T12:57:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20024 2024-06-06T06:21:17Z ddc:004 open_access

Algorithms for Halfplane Coverage and Related Problems Wang, Haitao Xue, Jie halfplane coverage circular coverage star-shaped polygon coverage ε-kernels 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}nlog^{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(nlog n) time, which improves the previously best algorithm of n^{4/3}2^{O(log^*n)} time and matches an Ω(nlog n) lower bound. Further, our techniques can be extended to solve a star-shaped polygon coverage problem in O(nlog n) time, which in turn leads to an O(nlog 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(nklog 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(nlog n) time. Our result thus answers the open question affirmatively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang and Jie Xue 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.79 urn:nbn:de:0030-drops-200248 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.79 eng https://creativecommons.org/licenses/by/4.0/legalcode