Algorithms for the line-constrained disk coverage and related problems
Algorithms for the line-constrained disk coverage and related problems
复制标题
线路约束磁盘覆盖算法及相关问题
DOI：
10.1016/j.comgeo.2022.101883
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wang, Haitao
中科院分区：
文献类型：
--
作者：
Pedersen, Logan;Wang, Haitao
给定平面上n个点的集合P和m个加权磁盘的集合S，磁盘覆盖问题要求总权重最小的磁盘子集覆盖P的所有点。这个问题是np困难的。在本文中，我们考虑了一个线约束的版本，其中所有的磁盘都以直线L为中心（而P的点可以在平面的任何地方）。我们提出了一个O ((m+ n) log （m+ n)+ κ log (m)）时间算法，其中κ是边界相交的磁盘对的数目。或者，我们也可以在O （n m log (m+ n)）时间内解决这个问题。对于所有磁盘具有相同半径的单位磁盘情况，运行时间可以减少到O (（n+ m) log (m+ n)）。此外，我们在O ((m+ n) log (m+ n)) time内分别求解了该问题的L∞和L 1情况，其中磁盘分别为正方形和菱形。我们进一步证明，我们的技术也可以用于解决其他几何覆盖问题。例如，在平面上给定一个集合P （n个点）和一个集合S （n个加权半平面），我们在O （n4log (n)）时间内解决一个问题，找到一个覆盖P的半平面子集，使它们的总权重最小。这改进了以前的最佳算法O （n 5）时间，几乎是线性因子。如果所有的半平面都是较低的半平面，那么我们的算法运行时间为O (n2log (n))，这比之前的最佳算法O （n4）时间提高了几乎一个二次因子。
Given a set P of n points and a set S of m weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of P. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line L (while points of P can be anywhere in the plane). We present an O ((m+ n) log(m+ n)+ κ log m) time algorithm for the problem, where κ is the number of pairs of disks whose boundaries intersect. Alternatively, we can also solve the problem in O (n m log(m+ n)) time. For the unit-disk case where all disks have the same radius, the running time can be reduced to O ((n+ m) log(m+ n)). In addition, we solve in O ((m+ n) log(m+ n)) time the L∞ and L 1 cases of the problem, in which the disks are squares and diamonds, respectively. We further demonstrate that our techniques can also be used to solve other geometric coverage problems. For example, given in the plane a set P of n points and a set S of n weighted half-planes, we solve in O (n 4 log n) time the problem of finding a subset of half-planes to cover P so that their total weight is minimized. This improves the previous best algorithm of O (n 5) time by almost a linear factor. If all half-planes are lower ones, then our algorithm runs in O (n 2 log n) time, which improves the previous best algorithm of O (n 4) time by almost a quadratic factor.