在三维空间中给定N个点，如何找到包含这些N个点的最小球？

Question

在三维空间中给定N个点，如何找到包含这些N个点的最小球？

- bit-question

---

这不是一个编程问题，而是一个数学问题。 - Ether

Answer 1

这个问题被称为最小外接球问题（可在Google上搜索此术语以找到有关它的教程和论文）。

这里是一个实现：http://www.inf.ethz.ch/personal/gaertner/miniball.html，用c++编写。

它的2D情况（找到一个圆来包含平面上的所有点）是计算几何课程中经典的例子。3D只是2D情况的简单扩展。

这个问题的一种算法是增量式的。你从4个点开始，它们固定了一个球体，当你添加第5个点时，有两种情况：

1. 点在球内，无需更新。 2. 点在球外。在这种情况下，您需要更新您的球体。然后一个非平凡的属性是这个新点必须在你的新球体上！

基于以上观察，您的问题变得更小。阅读这本书的第4.7节。它也可以在Google图书上找到。

- Yin Zhu

---

关于上述算法的一个重要注意事项是，你应该在点的随机排列上构建增量算法。否则，算法的最坏情况是O(n^2)。通过随机排列，你应该能够以很高的概率获得O(n log(n))的运行时间。 - undefined

Answer 2

针对这个问题，有几种算法和实现方法可用。

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

• 对于更高维度（比如说10,000），可以看看https://github.com/hbf/miniball，这是Gärtner、Kutz和Fischer提出的一种算法的实现（注意：我是其中的合著者之一）。

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

注意：如果你正在寻找一种计算最小包围球的球体的算法，你可以在计算几何算法库（CGAL）中找到一个C++实现。（你不需要使用CGAL的全部内容；只需提取所需的头文件和源文件即可。）

- Hbf

Answer 3

问题归结为找到N个点的凸包。大多数凸包算法，如分治、礼品包装或Jarvis March和Timothy Chan的算法也可以应用于3D。在所有这些算法中，Timothy Chan的算法是已知的最佳算法。

- Boolean