提问人：6502 提问时间：3/19/2019 最后编辑：Community6502 更新时间：4/28/2020 访问量：278
用不均匀的圆盘实现最佳覆盖
Optimal covering with non-uniform discs
问：
我可以使用哪种算法来搜索具有 n 个圆盘 （ x j， y j， r j ） 的 XY 平面有限区域的最佳（最小面积）覆盖？
我发现了很多关于固定半径圆盘的研究，但没有关于可变半径的研究。
n是固定的，但圆盘可以自由放置（它们不在指定的位置，并且它们的中心不需要在区域内）。该区域一般为非连接和非简单连接（可由多个部分组成，可有孔）。在我的具体情况下，由多个闭合多边形定义（使用奇偶填充规则）。
回顾一下：
输入：
XY 平面的有限区域（例如，描述为具有奇偶填充规则的闭合多边形的集合）
0 >整数
n
输出：
- 按中心和半径描述的圆盘列表，以便该区域的每个点都包含在至少一个圆盘中
nx[i], y[i]r[i]
最小 化：
- 圆盘联合覆盖的平面面积
例
在此示例中，输入是“A”形状。手动放置 10 个点，并计算覆盖该区域与 Voronoi 像元交叉点的最小圆圈。
我目前正在研究这种方法，该方法基于仅查找中心并使用该算法计算半径（搜索空间减少了 Rn，并且始终产生可接受的解决方案）。x[i], y[i]r[i]
答：
0赞
Aaron
4/28/2020
#1
这是一个非常酷的问题！我很高兴我偶然发现了这个。我完全意识到这已经有一年多的历史了，所以你可能不再关心它了，但我会以任何一种方式回答它，因为我喜欢谜语，这是一个有趣的谜语（假设我的解决方案甚至有效！
我会做的似乎类似于 Voronoi 图建议：
从问题的分层聚类解决方案开始。它不会有最小的面积，但它会用 N 个磁盘覆盖所有内容。
a. 注意：我不会使用 K-means，因为 K-Means 很容易陷入局部最小值。
然后，您可以使用梯度下降来移动圆盘的中心（损失是每个圆盘的总面积 - 计算为到该“集群”中点的混合距离），以获得更优化的解决方案。
我认为这里有一些警告，如果你有几个孤独的观点，它们可能会导致一些不受欢迎的解决方案。
显然没有证据表明这会起作用。你觉得怎么样？另外，你最终用了什么？
评论
n