如何用半径固定的不相交圆覆盖平面上一组圆？

Question

如何用半径固定的不相交圆覆盖平面上一组圆？

algorithmgeometrylanguage-agnosticmathematical-optimizationcomputational-geometry

6

所以，您有一个给定维度的表/区域，在这个区域内有孔（其中心点（x，y）和半径已知）。问题是，您需要用补丁覆盖这些孔。这些圆形补丁具有固定半径（例如：5的半径），不允许彼此重叠（但可以接触）。您可以使用任意数量的补丁，目标不是找到最优数量，而是看看是否可能覆盖每个孔。

我已经用KD树解决了类似的问题，但由于这个问题中孔的三维尺寸，我不确定如何解决。只是想找到正确方向的指针，而不是编码解决方案 :)

- John

这确实是一个非常有趣的问题！但请注意，您当前提出的问题并不适合在StackOverflow上进行。“指向正确方向”的问题并不是SO所关注的内容。在这里，您可以陈述一个明确定义的问题，该问题的性质应该是具有明确且正确答案的。您的问题属于“主观判断”或类似领域。因此，如果它被关闭，请不要感到太惊讶。无论如何，祝你好运 :-) - Alfe

确实是一个非常有趣的问题，它可能会在计算机科学堆栈交换上得到更多关注。但是你所说的“孔洞的三维性质”是什么意思？ - m.raynal

1

@m.raynal 上一次我使用KD树时，我处理的是点（x，y）。但是这个问题中我将同时拥有x、y和半径，因为我的数据集是圆（大小不同），而不是点。不确定它是否变成了“3D”，但似乎比标准的x，y点更难分割到空间划分树中 :) - John

我甚至不确定如何使用点而不是圆来解决这个问题。此外，我无法看出KD树如何帮助解决这个问题。如果您能简要解释一下原始解决方案的工作原理，那么它可能会有所帮助。 - SaiBot

你是否使用另一个账号在CS上转载了这篇内容？ - Peter Taylor

1

在我看来，你需要先找到几何解决方案，而不是关心效率和加速数据结构，比如kD树。我也认为这是一个非常棘手的问题。 - user1196549

2个回答

1

根据补丁和孔的大小，可能没有解决方案。

使用最紧凑的补丁数组的解决方案：

没有解决方案，因为孔比补丁大，这会导致未覆盖的区域：

没有解决方案，因为孔太靠近：

对于一般的构造，您可以从以孔为中心的补丁开始。然后按需要平移和旋转（围绕相邻补丁的中心）补丁：

- Ripi2

干杯。这对于用单个补丁覆盖多个孔也适用吗？假设每个孔的半径不同为1-3，而补丁的半径为5？ - John

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- saastn · Accepted Answer

你可能正在寻找一种分析性或至少是确定性解决方案。但恐怕这太复杂了，没有一个解决方案。元启发式算法（如EA）则可以应对这种问题，因为它们具有随机性质。当你决定采用这种方法时，你必须将你的问题转变为优化问题。

我尝试使用基本形式的DE算法来解决这个问题。为了定义一个优化问题，我假设一个解向量是由2*N个浮点变量组成的数组，其中N是孔的数量。这个数组表示补丁的X和Y坐标，因为最多需要N个补丁来覆盖N个孔。

代价函数（需要最小化）的定义如下：

Find closest patch to each hole
Find A1 as sum of uncovered areas of holes by their closest patchs
Find A2 as sum of intersection areas of active(!) patches
return max(A1, A2)

在这个函数中，一个活动补丁是指最靠近至少一个洞的补丁。这个定义被添加到问题中以涵盖你在对Ripi2答案的评论中提到的情况（当一个补丁覆盖两个洞时，就会有另一个无用的补丁）。更具体地说，假设有一个不是任何洞最近的补丁P1，H1是最接近这个补丁的洞，但它最接近的补丁是P2。因此，我们可以确定H1和P1的交集面积小于或等于H1和P2的交集面积。由于关于其最近的洞是真实的，所以对于所有其他洞也是如此，因此让我们认为它不存在！

这是一个示例：

请记住，这些算法从未保证找到全局最优解，但它们会提供一组次优解。