由于N点在3D空间中，如何找到包含这些N个点的最小球？

Given N points in a 3D space, how to find the smallest sphere that contains these N points?

推荐答案

这个问题称为最小包含球问题。 （谷歌这个术语来找到教程和文章就可以了）。

This problem is called minimal enclosing ball problem. (google this term to find tutorials and papers on it).

下面是一个实现： http://www.inf.ethz.ch/个人/盖特纳/ miniball.html 在C ++中。

Here's one implementation: http://www.inf.ethz.ch/personal/gaertner/miniball.html in c++.

该公司在二维情况下（找了一圈包围在一个平面上的所有点）就是一个典型的例子教导计算几何课程。三维仅仅是一个简单的扩展与2D情况。

Its 2d case (find a circle to enclose all points in a plane) is a classic example taught in computational geometry course. 3D is just a simple extension to the 2D case.

一个算法，这个问题是渐进式的。你开始连得4分，他们确定一个球体，当你加5个点，有两种情况：

One algorithm for this problem is incremental style. You start with 4 points and they fix a sphere, and when you add 5-th point, there are two cases:

点是在球体。不需要更新

the point is in the sphere. no need to update.

点之外。在这种情况下，你需要更新你的球。然后一个不平凡的特性是，这个新的点必须在新的领域！

outside the point. In this case, you need to update your sphere. Then a non-trivial property is that this new point must be on your new sphere!

根据上述的观察中，您的问题变得更小。阅读这本书。它也可在谷歌图书。

Based on the above observation, your problem gets smaller. Read section 4.7 of this book. It is also available on google book.