用不均匀的光盘进行最佳覆盖 [英] Optimal covering with non-uniform discs

问题描述

使用 n 个光盘(x _j ，y _j ，r _j )吗?

我在固定半径的圆盘上发现了很多研究，但对于可变半径却一无所获.

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

回顾:

输入:

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

• 整数n> 0

输出:

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

最小化:

• 圆盘结合所覆盖的平面区域

示例

在此示例中，输入为"A"形.手动放置10个点，并计算出覆盖该区域与Voronoi细胞相交的最小圆.

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

解决方案

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

我会做的事情似乎与Voronoi图建议类似:

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

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

2. 然后，您可能可以使用梯度下降来移动磁盘的中心(损失是每个磁盘的总面积-计算为到该集群"中各点的最小距离)更好的解决方案.

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

很显然，没有证据证明这行得通.你怎么认为?另外，您最终使用了什么?

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_j, y_j, r_j ) ?

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

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).

To recap:

Input:

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

• an integer number n > 0

Output:

• 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

Minimizing:

• the area of the plane covered by the union of the discs

Example

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.

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!).

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

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

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

2. 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?

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