algorithm - 在二维平面上找到(近)最小覆盖圆盘集

Question

好吧，假设我有一堆光盘放在已知固定位置的飞机上。每个圆盘的半径为 1 个单位。该平面完全被一组圆盘覆盖，事实上，它被一组圆盘广泛覆盖，在某些区域覆盖了一两个数量级。我想找到仍然完全覆盖飞机的光盘子集。最佳是好的，但不是必需的。

这是之前的插图:

这是后图:

在我看来，Delaunay 三角剖分存在一个双重问题，但我不太确定这对我有帮助。我也知道这与计算几何中的圆盘覆盖问题相似但不相同。这是一个我不知道名字的标准问题吗？

在我看来，可能的方法包括使用局部贪婪搜索来增加覆盖集，并使用最近对查询迭代地一次删除一个圆盘。我不确定两者是否都能保证正常工作，而且我还没有研究过细节。

哦，如果您没有猜到的话，应用程序是在进行查询时查找邮政编码质心的子样本以覆盖 map ，因此 n 约为 50,000。

Answer 1

游戏计划

以下基本上只是对您的问题的更精确的重述，但它可能会有所帮助:

1. 枚举绘制所有圆盘边界时产生的平面中的每个连接区域。根据假设，这些区域中的每一个都被 1 个或多个磁盘覆盖。
2. 每个区域都是一个“被覆盖的东西”，每个磁盘都是一个“覆盖的东西”。找到 minimum set cover在这组区域上。不幸的是，这是 NP-hard。

这可能不会利用问题中所有可用的结构，但它肯定会为您提供最佳答案。

枚举区域

在步骤 1 中枚举区域并记录每个磁盘覆盖的区域是棘手的部分。区域通常不是凸面的，这使得相交测试变得棘手，并且您添加的每个圆都可能使区域数量翻倍。以下是我的处理方法:

忘掉每个区域的实际位置，只根据它在内部和外部的磁盘来定义区域。 IE。一个区域由长度为 n 的 0/1 值向量定义，每个值表示该磁盘内部或外部的区域是否包含在交集中——所讨论的区域是由所有这 n 个区域相交形成的。所以原则上你最多可以有 2^n 个区域，但实际上一些(大多数)向量会产生空区域，因为它们需要与两个没有交集的圆盘相交——谢天谢地，这很容易测试。递归生成所有非空区域应该很简单，除了...

坏消息

不幸的是，我现在发现执行完整交叉测试是是必要的，因为并不总是能够判断区域何时为空。关键的反例是，给定两个有少量重叠的圆盘 A 和 B，另一个圆盘 C 与 A 和 B 分别重叠，这取决于所有 3 个圆盘的位置，所有 3 个圆盘的交集可能会也可能不会是非空的。 (要看到这一点，请在绘图程序中以 50% 的不透明度绘制 3 个不同颜色的圆盘，然后移动它们。)

可行的技巧

由于生成非空区域的确切列表看起来需要大量工作并且由于相交测试需要很长时间，并且您声称不需要最佳解决方案，您可以尝试使用网格样本点作为“要覆盖的事物”的集合，而不是非空区域的确切列表。确定哪些磁盘覆盖了给定的样本点非常简单。然后像以前一样解决最大集合覆盖。

要确定没有间隙，请重新运行几次，每次随机抖动样本点的坐标。增加样本点的密度，直到最终结果没有变化。