用不均匀的光盘进行最佳覆盖
650*_*502 6 algorithm math optimization geometry 2d
我可以使用哪种算法来搜索n个光盘（x j，y j，r j）覆盖XY平面有限区域的最佳（最小面积）？
我发现有许多关于固定半径光盘的研究，但关于可变半径却没有任何研究。
n固定，但光盘可以自由放置（它们不在指定的位置，并且它们的中心不需要在区域内）。该区域通常是非连接和非简单连接的（可以由多个部分组成并且可以具有孔）。在我的特定情况下，是由多个封闭的多边形定义的（使用奇偶填充规则）。
回顾一下：
输入：
XY平面的有限区域（例如，描述为具有奇偶填充规则的闭合多边形的集合）
n> 0 的整数
输出：
n用中心x[i], y[i]和半径描述的光盘列表，r[i]以便该区域的每个点都包含在至少一张光盘中
最小化：
- 圆盘结合所覆盖的平面区域
例
在此示例中，输入为“ A”形。手动放置十个点，并计算出覆盖该区域与Voronoi单元的交点的最小圆。
我目前正在研究仅基于寻找中心x[i], y[i]并r[i]使用此算法计算半径的方法（搜索空间减少？n并始终产生可接受的解决方案）。
这是一个非常酷的问题！我很高兴我偶然发现了这个。我完全意识到这已经有一年多了，所以你可能不再关心它了，但我会以任何一种方式回答它，因为我喜欢谜语，而且这是一个有趣的谜语（假设我的解决方案甚至有效！）。
我要做的似乎与 Voronoi 图建议类似：
从问题的层次聚类解决方案开始。它不会有最小的面积，但它会用 N 个磁盘覆盖所有内容。
A。注意：我不会使用 K 均值，因为 K 均值很容易陷入局部最小值。
然后，您可能可以使用梯度下降来移动圆盘的中心（损失是每个圆盘的总面积——计算为到该“簇”内的点的混合距离）以获得更优化的解决方案。
我认为这里需要注意的是，如果你有一些孤立的点，它们可能会导致一些不良的解决方案。
显然没有证据表明这会起作用。你怎么认为？另外，你最后用的是什么？