如何找到包含一些给定点的最小圆？

Question

我有一些点（2D坐标），希望找到一个最小的圆，包含所有这些点。算法不必非常高效（虽然自然而然会很好）。

- Mnementh

---

可能是二维平面上覆盖给定点的最小圆的重复问题；同一用户有一个相同的答案，而且我认为另一个问题的措辞更好。此版本中仅有链接的答案也不太好... - Benjamin

Answer 1

这是所谓的最小包围球问题（在您的情况下，最小包含圆），也称为Miniball。 对于这个问题，有几种算法和实现 - 所有以下都是线性时间解决方案（即，给定n个球，如果考虑固定维度d，则运行时间为O（n）， 在您的情况下，d = 2）：

• 对于2D和3D， Gärtner的实现可能是最快的。

• 对于更高的维度（高达10,000），请查看https://github.com/hbf/miniball，这是Gärtner，Kutz和Fischer算法的实现（注意：我是其中一位合著者）。

• 对于非常高的维度，核心集（近似）算法将更快。

注意：如果您正在寻找计算球体的最小包围球的算法，则可以在Computational Geometry Algorithms Library（CGAL）中找到C ++实现。 （您不需要使用CGAL的所有部分;只需提取所需的头文件和源文件即可。）

- Hbf