在二维平面上，给定一些点，找到能够覆盖所有点的最小圆形。

Question

8

问题：在二维平面上给定N个点，覆盖这些点的最小可能圆的直径是多少？

解决此问题的最有效算法是什么，它是如何工作的？

- Leonid

这个问题以前被问过，但要是我能找到就好了。 - Aryabhatta

2

这是关于__最小圆问题__的内容，请在此处查看：http://en.wikipedia.org/wiki/Smallest_circle_problem - Jack

这里有一个“重复”的答案，虽然像我的回答一样并不是很好：https://dev59.com/V3A75IYBdhLWcg3wy8Ui - Benjamin

2

Nayuki.io有这个脚本：https://www.nayuki.io/page/smallest-enclosing-circle - kuanb

3个回答

6

对于“最小包围球”问题，有几种算法和实现方法可供选择。

对于二维和三维，Gärtner的实现可能是最快的。
对于更高的维度（比如10,000维），可以看一下https://github.com/hbf/miniball，这是一个由Gärtner、Kutz和Fischer提出的算法的实现（注意：我是其中的合著者之一）。
对于非常高的维度，使用核心集（近似）算法效果更好。

注意：如果您正在寻找计算“球之间的最小包围球”的算法，可以在计算几何算法库（CGAL）中找到一个C++实现。（您不需要使用CGAL的所有功能，只需提取所需的头文件和源代码即可。）

- Hbf

这个算法在球面上的点上能够很好地工作吗？我正在尝试解决地理定位问题。 - Thadeu Melo

1

最远点沃罗诺伊图方法

http://www.dma.fi.upm.es/mabellanas/tfcs/fvd/algorithm.html

这种方法对于二维问题非常有效，它是非迭代的且（几乎可以肯定）保证精确。我怀疑它在更高的维度上无法很好地推广，这就是为什么文献中很少关注它的原因。

如果有兴趣的话，我会在这里进行描述——我认为上面的链接有点难以理解。

- agentp

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

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

- Benjamin · Accepted Answer

这是最小圆问题。参考文献中提供了建议算法的链接。

引用块：

E.Welzl，《最小外接圆(球体和椭球体)》，载于H. Maurer（主编）《计算机科学的新成果与新趋势》, 计算机科学讲义, Vol. 555, Springer-Verlag, 359–37 (1991)

是“最快”的算法的参考文献。