最小覆盖圆

Question

最小覆盖圆

algorithmmathematical-optimization

5

平面上有n个点，如何近似地找到一个圆的最小半径，以覆盖其中k个点？假设n小于10^4。

在维基百科中，对于k==n的情况有大量信息，但我没有找到关于一般情况的信息。

- se0808

1

这并不是一个真正的编程问题，更适合在https://cs.stackexchange.com/上提问。 - kebs

你将不得不通过蛮力来解决这个问题。比如，如果n==100且k==3，那么你只需寻找具有最小圆的每组3个点中的一个。你可以通过检查任意两点之间的距离是否大于迄今为止发现的最小直径来快速排除一些组合。 - Jonathan M

2

这个问题似乎不适合本站，因为它涉及算法设计而非实现。该问题已经被转发到了计算机科学板块（http://cs.stackexchange.com/questions/31960/minimal-covering-circle），在那里它是完全适合的。 - Gilles 'SO- stop being evil'

1

我们在 Meta 上已经多次讨论过这个问题。像这样的问题在这里是默认主题。 - David Eisenstat

3个回答

2

给定一个候选半径 r，您可以通过取每对点 (p1, p2) 并查看半径为 r 的两个圆中分别包含多少点来找到可以包含的最大点数。知道了这一点，您可以二分搜索最小的 r，使得某个半径为 r 的圆包含 k 个或更多点。

- tmyklebu

是的，但不幸的是，时间复杂度为O(n^3)，其中n=10^4。 - se0808

不是这样的。修复 p1。除了 p1 之外还有 n-1 个点。在 p1 上固定半径为r的圆，并将其旋转；每个除 p1 之外的点最多在每次旋转中进入和离开圆一次。 - tmyklebu

那么，使用O(iterations * n^2 log n)和来自排序的O(n log n) - 但无论如何似乎都太慢了。 - se0808

1

@tmyklebu 如果您旋转半线并在穿过点时跟踪点交叉的角度扫描，我同意这比每个点p1的O(n ^ 2)更快。但您正在旋转半径为r的圆，并且弄清楚点何时进入和离开是非常棘手的。我建议对如何击败O(n ^ 3)进行更详细的说明，要记住二进制搜索步数与数字精度相关，而数字精度可能是任意的。 - user2566092

用户2566092：修复r和p1。可以预先计算进入和离开圆的角度并对其进行排序，然后它将花费线性时间 - 就像旋转线一样。 - se0808

显示剩余2条评论

-2

一种想法是将所有点的平均值作为中心，然后增加半径直到覆盖k个点。在相当均匀的分布下，这可能会做得很好，但对于“聚集”数据则会失败。例如，如果点位于两个远离彼此的紧密簇中，并且k足够小以只需要其中一个，则这将失败。如果存在这种聚类的可能性，请考虑使用聚类算法来识别局部聚类，然后如果其中一个包含足够的点，则仅在该聚类上使用该算法。

- MattPutnam

1

这样做不行。当您考虑不同的k点集时，中心会发生变化。请参见我在上面对OP的评论。 - Jonathan M

OP也说“大约”，我理解为找到一个可以接受的答案，但不一定是最优解。 - MattPutnam

1

@se0808，你在原帖中所说的“approximately”是什么意思？有多大程度的近似？是最小值的10%还是50%之内？ - Jonathan M

@Johathan M，给定精度 - 我的意思是类似于二分查找。 - se0808

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

这是一个算法，给定半径r>0和近似常数c>0，要么返回一个半径为(1+c)r的圆形，至少包含k个点，要么声明没有一个严格半径为r的圆形包含至少k个点。运行时间为O(n(1+k^-1c^-2log c^-1))，与二进制搜索结合使用以获得足够粗略的估计时，应该比tmyklebu的算法更快。（要初始化搜索，可以在时间O(n^2)内通过循环遍历点并运行quickselect找到第k个最接近的其他点来获取r的2逼近）。

按照(x,y)的坐标将点分割到标记为(floor(x/(2r)), floor(y/(2r)))的正方形中。每个半径为r的圆形的内部最多重叠四个格子。如果存在半径为r的圆形包含至少k个点，则存在i，j使得(i，j)，(i，j+1)，(i+1，j)，(i+1，j+1)这四个方格共包含至少k个点。

对于每个子问题，将每个涉及点(x,y)放入较小的正方形格子(floor(x/w), floor(y/w))中，其中w=cr/(3sqrt(1/2))是足够小的宽度。现在准备一个O（c^-1）乘O（c^-1）的矩阵，其中每个条目告诉相应的正方形中包含多少点。在二维中与一个全包含于半径为(1+c)r圆内的方格的零一矩阵卷积。后者的矩阵可能看起来像：

现在我们知道了网格上每个中心点的数量，该数量被半径为r的圆所包含的点数下限和半径为(1+c) r的圆所包含的点数上限所限制。