.png){kind=icon}
返回
On line-separable weighted unit-disk coverage and related problems
.png){kind=icon}
PRE
AI
DOI：10.1016/j.comgeo.2025.102188.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定平面上一组包含n个点的集合P和一组包含n个带权圆盘的集合S，圆盘覆盖问题旨在计算一个总权值最小的圆盘子集，使得该子集中圆盘的并集覆盖P中的所有点。该问题属于NP难问题。本文考虑了该问题的一种线可分单位圆盘版本，其中所有圆盘具有相同半径，且它们的中心与P中的点由一条线& ell;隔开。我们为该问题提出了一种时间复杂度为O(n^{3/2} log^2 n)的算法。这改进了之前O(n^2 log n)时间复杂度的最佳结果。我们的结果进一步为半平面覆盖问题（即使用n个带权半平面覆盖n个点）提出了一种时间复杂度为O(n^{7/2} log^2 n)的算法，优于之前的O(n^4 log n)时间复杂度解。若所有半平面均为下半平面，我们的算法运行时间为O(n^{3/2} log^2 n)，而之前的最佳算法需要O(n^2 log n)时间。通过使用对偶性，在相同设置下，点集的击中集问题可以用类似的时间复杂度解决。 (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Keyword:
Line-separable
Unit disks
Halfplanes
Geometric coverage
Geometric hitting set
期刊
C
IF:
0.7
论文数:
14
被引数:
0
机构
引用论文
.png){kind=icon}
没有更多内容
没有更多内容