非均匀圆盘的最佳覆盖

问题描述

我可以使用什么样的算法来搜索具有 n 个圆盘的 XY 平面有限区域的最优(最小面积)覆盖( x, y, r ) ?

What kind of algorithm can I use to search for an optimal (minimum area) covering of a limited region of the XY plane with n discs ( x, y, r ) ?

我发现了很多关于固定半径圆盘的研究，但没有关于可变半径的研究.

I've found many investigations on fixed radius discs, but nothing about variable radius.

n 是固定的，但光盘可以自由放置(它们没有在指定的位置，它们的中心不需要在区域内).该区域一般是非连通和非单连通的(可以由多个部分组成，可以有孔).在我的具体情况下是由多个闭合多边形定义的(使用奇偶填充规则).

n is fixed but the discs can be placed freely (they're not in assigned positions and their centers are not required to be inside the region). The region is in general non-connected and non-simply connected (can be composed by multiple parts and can have holes). In my specific case is defined by multiple closed polygons (using odd-even filling rule).

总结:

输入:

• XY 平面的有限区域(例如，描述为具有奇偶填充规则的闭合多边形的集合)

• a limited area of the XY plane (e.g. described as a collection of closed polygons with odd-even filling rule)

一个整数n >0

输出:

• 由中心 x[i], y[i] 和半径 r[i] 描述的 n 个圆盘的列表，使得每个该区域的点至少包含在一张光盘中

• a list of n discs described by center x[i], y[i] and radius r[i] so that every point of the area is contained in at least one disc

最小化:

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

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

In this example the input was the "A" shape. Ten points were placed manually and minimal circles covering the intersection of the area with the Voronoi cells were computed.

我目前正在研究基于仅查找中心 x[i], y[i] 并使用此计算半径 r[i] 的方法算法(搜索空间减少了ℝ并且总是产生可接受的解决方案).

I'm currently investigating the approach based on just looking for the centers x[i], y[i] and computing the radiuses r[i] with this algorithm (search space is reduced by ℝ and always produces an acceptable solution).

推荐答案

这是一个很酷的问题！我很高兴我偶然发现了这个.我完全意识到这已经一年多了，所以你可能不再关心它了，但我会以任何一种方式回答它，因为我喜欢谜语而且这是一个有趣的谜语(假设我的解决方案甚至有效！).

This is a really cool problem! I'm glad I stumbled on this one. I fully realize that this is over a year old, so you probably don't care about it anymore, but I'll answer it either way because I like riddles and this was a fun one (assuming my solution even works!).

我会做的似乎类似于 Voronoi 图的建议:

What I would do seems similar to the Voronoi diagram suggestion:

1. 从问题的层次聚类解决方案开始.它不会有最小的面积，但它会用 N 个磁盘覆盖所有内容.

1. Start with a hierarchical clustering solution to the problem. It won't have minimal area, but it will cover everything with N disks.

一个.注意:我不会使用 K 均值，因为 K 均值很容易陷入局部最小值.

a. Note: I wouldn't use K-means because K-Means tends to get caught in local minima quite easily.

然后你可能可以使用梯度下降来移动圆盘的中心(损失是每个圆盘的总面积——计算为到这个集群"内的点的混合距离)来得到你一个更优化的解决方案.

You could probably then use gradient descent to move the centers of the disks (with the loss being the total area of each disk -- computed as the miximal distance to the points within this "cluster") to get you a more optimal solution.

我认为这里有一些警告，如果您有一些孤立点，它们可能会导致一些不受欢迎的解决方案.

I think some caveats here would be if you have a few lone points, they might lead to some undesirable solutions.

显然没有证据表明这行得通.你怎么认为?另外，你最后用的是什么?

There's obviously no proof that this would work. What do you think? Also, what did you end up using?

这篇关于非均匀圆盘的最佳覆盖的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！