2026-07-24T09:41:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19353 2024-03-06T11:03:51Z ddc:004 open_access

On the Line-Separable Unit-Disk Coverage and Related Problems Liu, Gang Wang, Haitao disk coverage line-separable unit-disk line-constrained half-planes Given a set P of n points and a set S of m disks in the plane, the disk coverage problem asks for a smallest subset of disks that together cover all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line 𝓁. We present an m^{2/3} n^{2/3} 2^O(log^*(m+n)) + O((n+m)log(n+m)) time algorithm for the problem. This improves the previously best result of O(nm + n log n) time. Our techniques also solve the line-constrained version of the problem, where centers of all disks of S are located on a line 𝓁 while points of P can be anywhere in the plane. Our algorithm runs in O(m√n + (n+m)log(n+m)) time, which improves the previously best result of O(nm log(m+n)) time. In addition, our results lead to an algorithm of n^{10/3} 2^O(log^*n) time for a half-plane coverage problem (given n half-planes and n points, find a smallest subset of half-planes covering all points); this improves the previously best algorithm of O(n⁴log n) time. Further, if all half-planes are lower ones, our algorithm runs in n^{4/3} 2^O(log^*n) time while the previously best algorithm takes O(n²log n) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gang Liu and Haitao Wang 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.51 urn:nbn:de:0030-drops-193535 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.51 eng https://creativecommons.org/licenses/by/4.0/legalcode