半径为r的圆的最小数量,以覆盖n个点

Question

覆盖所有n点所需的半径为r的最小圆数是多少？r和n将作为输入给出,接着是n对整数,表示n个点的xy坐标.r是实数且大于0.n <20.

如果该点位于圆内,则圆圈覆盖一个点.如果点与圆心之间的距离小于或等于r,则点位于圆内.

Answer 1

这可能不是最佳解决方案,但尝试对其进行优化.

算法基于随机抽样:

1. 在地图上生成N个圆圈
2. 删除所有未覆盖任何点的圆圈
3. 按被覆盖点数减少的圆圈排序
4. Foreach圆圈(已排序) - 标记由圆圈覆盖的点.如果圆圈未覆盖任何新点,请从列表中删除.

以下是您可以预览的代码:http://jsfiddle.net/rpr8qq4t/示例结果(每30分13个圆圈):

参数化:

  var POINTS_NUMBER = 30;
  var RADIUS = 50;
  var SAMPLE_COUNT = 400;

可能会添加一些优化(例如,某些圈子可能会过早地从列表中排除)

编辑:

1. 步骤1中的更改​​带来了更好的结果:为每个点生成N个圆圈(至少覆盖点的圆圈)新版本:http://jsfiddle.net/nwvao72r/3/

编辑2(最终算法)

最后:

1. Foreach点生成N = 10个圆圈,随机距离小于R点(圆的半径,所以我们确定每个圆圈至少有一个点属于它,每个点属于至少一个圆圈)
2. 重复直到覆盖所有点:
   • 得到圆圈覆盖最大未覆盖点数.标记点覆盖.

这是给我带来最佳效果的版本,你可以在这里查看 http://jsfiddle.net/nwvao72r/4/ 这里 每30分平均12圈.

Answer 2

我确定这个问题是NP难的,尽管我不打算在这里证明这一点.

如果它是NP难的,那么为了找到保证最优的解决方案,我建议采用以下方法:

1. 查找所有"好的"潜在圈子展示位置,以及每个记录中包含哪些点数.
2. 用这些点解决集合覆盖问题.(这个问题是NP难的.)

好的圈子位置

给定2个小于2r的点,正好有两个半径为r的圆圈通过这些点:

[编辑:我对"最好的"圈子的原始描述是错误的,虽然这不会导致问题 - 感谢评论家乔治描述正确的思考方式.]

如果圆圈覆盖了一组最大点(意味着圆圈无法重新定位以覆盖同一组点加上至少1个点),则该圆圈可以滑动,直到其边界恰好触及它所覆盖的两个点 - - 比如说,向左滑动直到它接触到已经覆盖的点,然后围绕这个触摸点顺时针旋转它,直到它接触另一个已经覆盖的点.这个移动的圆圈将完全覆盖原始圆圈所覆盖的一组点.此外,我们永远不需要考虑覆盖非最大点集的圆,因为覆盖这些点和更多点的最大圆至少同样有用并且不再花费更多.这意味着我们只需要考虑触及两点的圆圈.如果我们为输入中每个足够接近的点生成两个圆,我们将生成我们可能需要的所有圆.

因此,我们的潜在圆圈池每对点最多包含2个圆圈,总共最多有n*(n-1)个潜在圆圈.(通常会有更少的,因为一些双点通常会进一步比2R开,并且因此不能由半径为r的单个圆圈覆盖.)此外,我们需要为进一步比2R从每个点的额外圆任何另一点 - 这些圈子也可能以这些远程点为中心.

设置封面

我们真正关心的是每个潜在圈子所涵盖的一组点.因此,对于每个潜在的圈子,找到它所涵盖的点.这可以在整个O(n ^ 3)时间内完成,对每个潜在的圆使用O(n)通过.为了加快速度,如果我们发现两个不同的圆圈覆盖完全相同的一组点,我们只需要保留其中一个圆圈(覆盖点集).此外,我们可以丢弃任何覆盖点集,这是一些其他覆盖点集的子集 - 在这种情况下,最好选择较大的覆盖点集.

最后,我们有一组覆盖点集,我们希望找到涵盖每个点的这些集的最小子集.这是设置封面问题.我不知道一个特定的算法来解决这个问题,但分支限界是此类问题的标准方法-这是经常比一个简单的详尽回溯搜索快得多.我首先通过首先找到一个(或多个)启发式解决方案来进行搜索,希望产生一个良好的上限,这将减少分支和边界搜索时间.我认为,即使是在这个最好的算法需要指数时间在最坏的情况下,虽然我认为这将是可控的对于n <20为有最多19*18 = 342套不同点.

Answer 3

平铺然后摇晃

1. TILE：找到包围所有点的矩形
2. 用间隔为 r * sqrt(2) 的圆圈平铺矩形区域。
3. 对于每个点，计算它们是哪些圆以及每个圆中有哪些点。
4. 删除任何没有点的圆。
5. 删除仅包含多个圆中包含的点的任何圆。
6. 重复5，直到没有更多。
7. 摇动：对于每个圆圈：尝试移动它，看看它是否可以覆盖其原始点加上最多的新点，然后执行此操作。
8. 再次执行 4 和 5。
9. 重复 7，直到摇动不会改变哪些圆点所在或时间耗尽。

步骤 2，如果平铺非常稀疏，可以通过逐步遍历每个点并仅计算/保留那些包含点的圆来优化平铺。

Answer 4

摘自 Gautam K. Das 等人的论文“On the Discrete Unit Disk Cover Problem”。阿尔：

最小几何磁盘盖。在最小几何圆盘覆盖问题中，输入由平面中的一组点组成，问题是找到一组具有最小基数的单位圆盘，其并集覆盖了这些点。与 DUDC 不同，磁盘中心不限于从给定的离散集合中选择，而是可以以平面中的任意点为中心。同样，这个问题是 NP-hard [9] 并且有一个 PTAS 解决方案 [11, 12]。

参考：

9. R. Fowler、M. Paterson 和 S. Tanimoto，平面中的最优包装和覆盖是 NP 完全的，信息处理快报，第 12 卷，第 133-137 页，1981。
10. G. Frederickson，平面图中最短路径的快速算法，以及应用，SIAM J. on Computing，第 16 卷，第 1004-1022 页，1987 年。
11. T. Gonzalez，涵盖多维空间中的一组点，信息处理快报，第 40 卷，第 181-188 页，1991 年。
12. D. Hochbaum 和 W. Maass，图像处理和 VLSI 中覆盖和打包问题的近似方案，J. ACM，第 32 卷，第 130-136 页，1985 年。

Answer 5

如果您将n圆（半径为r）全部放置在每个点的中心，则查找最大重叠的区域/点并将新圆（半径为r）放置在该区域的中心。我不确定这是否是解决该问题的最佳方法（如果这是解决该问题的方法，除了暴力方法之外），我确信您可以通过相当多的数学来实现它，并且从而降低解决方案的运行时复杂性。希望这可以帮助。请给予反馈。