在3D空間中給定N個點，如何找到包含這N個點的最小球體？

Question

在3D空間中給定N個點，如何找到包含這N個點的最小球體？

Answer 1

這個問題被稱爲最小封閉球問題。 （谷歌這個詞來尋找教程和論文）。

下面是一個實現：http://www.inf.ethz.ch/personal/gaertner/miniball.html在C++中。

它的第2種情況（找到一個圓圈以包圍飛機上的所有點）是計算幾何課程中教授的經典示例。 3D只是2D情況下的一個簡單擴展。

這個問題的一種算法是增量式。你開始連得4分，他們修復了球，當你加5個點，有兩種情況：

1. 點是在球體。無需更新。

2. 以外的點。在這種情況下，你需要更新你的球體。然後一個非平凡的財產是這個新點必須在你的新領域！

基於上述觀察，您的問題變得更小。閱讀this book的第4.7節。它也可以在谷歌的書上。

Answer 2

問題歸結爲找到N個點的凸包。大多數像分而治之的凸包算法，禮物包裝或Jarvis March和Timothy Chan的算法都可以應用於3D。在所有這些算法中，Timothy Chan的算法是已知的最佳算法。

Answer 3

這個問題有幾種算法和實現。

• 對於2D和3D，Gärtner's implementation可能是最快的。對於更高維度（高達10,000，比如說），看看https://github.com/hbf/miniball，這是Gärtner，Kutz和Fischer算法的實現（注：我是其中一個合着者）。

• 對於非常非常高的尺寸，核心集（近似值）算法會更快。

注：如果你正在尋找一種算法來計算領域的最小包圍球，你會發現在一個Computational Geometry Algorithms Library (CGAL) C++實現。 （您不需要使用全部CGAL;只需提取所需的頭文件和源文件。）