非均匀圆盘的最优覆盖

Question

我可以使用什么算法来搜索一个有限的XY平面区域的最优（最小面积）覆盖，其中包含n个圆盘（xj，yj，rj）？我已经找到了许多关于固定半径圆盘的研究，但关于可变半径的研究却没有找到。n是固定的，但圆盘可以自由放置（它们不在指定位置，它们的中心也不需要在区域内）。该区域通常是非连通和非单连通的（可以由多个部分组成并且可以有孔）。在我的特定情况下，它由多个封闭多边形定义（使用奇偶填充规则）。

总结一下：

输入：

- XY平面的有限区域（例如，用奇偶填充规则的封闭多边形集合描述） - 整数n> 0

输出：

- 由中心x[i]，y[i]和半径r[i]描述的n个圆盘列表，以便区域的每个点都包含在至少一个圆盘中

最小化：

• 由圆盘并集覆盖的平面面积

示例

在这个例子中，输入是"A"形状。手动放置了十个点，并计算了覆盖 Voronoi 单元格与该区域相交的最小圆。

我目前正在研究基于查找中心点 x[i], y[i] 并使用此算法计算半径 r[i] 的方法（搜索空间缩小到 ℝⁿ，并始终产生可接受的解决方案）。

- 6502

---

进化算法应该提供一个合理的启发式方法。也许一些二次规划方法（使用圆方程的二次约束）可以得出最优解。 - John Coleman

@j_random_hacker：圆心和半径的位置是自由的...我必须优化圆的并集的面积。没有规定要选择哪些圆盘（甚至半径）。 - 6502

@j_random_hacker：是的，完全正确：不应该遗漏任何东西（区域中的所有点都应该至少被一个圆盘覆盖），但我想要最小化圆盘外部覆盖区域的面积（即，我希望圆盘覆盖的总面积最小，但这个面积显然不能小于区域的面积）。 - 6502

@mikuszefski “n” 似乎是问题的一个参数，这将排除任意小半径解决方案。 - John Coleman

我明白了。恐怕我没有看到一个整洁的解决方案...长而窄的目标区域将会带来困难，似乎难以避免在增加圆盘时创建此形状的“剩余碎片”。 - j_random_hacker

Answer 1

这是一个非常酷的问题！我很高兴能够偶然发现它。我完全意识到这已经过去一年了，所以你可能不再关心它，但我会回答它，因为我喜欢谜题，而且这个很有趣（假设我的解决方案有效！）。

我会做的事情似乎类似于沃罗诺伊图建议：

1. 从分层聚类解决方案开始。它可能没有最小面积，但它将用N个圆盘覆盖所有内容。

   a. 注意：我不会使用K-means，因为K-Means很容易陷入局部最小值。

2. 然后，您可以使用梯度下降来移动圆盘的中心（损失为每个圆盘的总面积--计算为该“簇”内点之间的最大距离），以获得更优化的解决方案。

我认为这里的一些注意事项是，如果您有一些孤立的点，它们可能会导致一些不良的解决方案。

显然没有证据表明这会起作用。你觉得呢？另外，你最终使用了什么？

- Aaron