一個不規則形狀，比如某地地圖，如何用一個半徑最小的圓把它完全包圍起來？

12-06

如果是物理老師可能會這樣回答：先用垂直法找到重心，然後找半徑,但我想要純數學方法解決

另外可能有人會說不提供具體圖形無法解答，那麼我們設定一個好了：比例尺1:50km的山東省地圖（陸地部分）求最小圓半徑

最小圓問題有一個漂亮的遞歸解法Smallest enclosing disks (balls and ellipsoids)，時間複雜度為 $O(n)$ 。

function B_MINIDISK(P,R) if P == ? or |R| == 3 then D = b_md(?, R) else choose random p in P D = B_MINIDISK(P - {p}, R) if p not in D then D = B_MINIDISK(P - {p}, R ∪ {p}) return D

function MINIDISK(P) return B_MINIDISK(P, ?)

簡單描述這個演算法的話，就是將平面上的點集分為兩個部分 $P$ 和 $R$ 。其中 $P$ 表示在最小圓內部的點集， $R$ 表示恰好在最小圓邊界上的點。初始狀態下，集合 $P$ 當中包含所有的平面上的點，集合 $R$ 是 $emptyset$ 。然後進入迭代當中，該演算法將從集合 $P$ 中任選一點 $p$ ，將點 $p$ 從 $P$ 中去除，接著遞歸計算內部包含 $P-{p}$ 邊界上包含 $R$ 的最小圓 $D$ 。判斷點 $p$ 是不是在這個圓 $D$ 當中。

如果在的話，那說明點 $p$ 不是在最終結果的最小圓邊界上的，也就說明這個遞歸計算出的圓 $D$ 就是我們要的答案了。如果不在的話，那我們就非常幸運地確定了點p肯定就是我們最終結果的最小圓邊界上的點。那麼我們就接著遞歸計算內部包含 $P-{p}$ 邊界上包含 $Rcup{p}$ 的最小圓出來，這個遞歸計算出來的結果，也就是我們要求的最終答案。

本質上來看，這個演算法就是在不斷地將不在最小圓邊界上的點從 $P$ 中去除，因為它們並不會影響最終結果；而將在最小圓邊界上的點添加到 $R$ 當中。所以該遞歸演算法的終止條件是要麼 $P=emptyset$ 了，已經沒有點可以從 $P$ 中被去除了；要麼 $left|R ight|=3$ 了，也即確定了3個在最小圓邊界上的點，從而確定了這個最小圓。

Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids) (pp. 359-370). Springer Berlin Heidelberg.

Smallest-circle problem （minimal enclosing circle problem, MEC）現時的最優演算法應該是[1]，它的運行時間平均複雜度是 $O(n)$ 的。

評論中提及，形狀若是曲線，就不可用點集。我找到另一個相關演算法[2]，計算曲線集的MEC，它也是平均複雜度 $O(n)$ 的。

[1] Welzl, Emo. Smallest enclosing disks (balls and ellipsoids). Springer Berlin Heidelberg, 1991. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46.1450rep=rep1type=pdf
[2] Gill, Barequet, Elber Gershon, and Myung-Soo Kim. "Computing the minimum enclosing circle of a set of planar curves." Computer-Aided Design and Applications 2.1-4 (2005): 301-308. http://3map.snu.ac.kr/mskim/ftp/ecc-cad05.pdf

重心法顯然是錯的。

物理方法的話，不知道有沒有那種理想的真空中的球形雞。呃，不對，不是真空，一個大氣壓下的球形雞……把東西塞進球形雞里，給外面加壓，則雞逐漸縮小，但是仍然保持球狀，直到被裡面的東西頂住發生形變為止。在那個剛剛被頂住的瞬間測量一下球形雞的半徑就好了。

呃，我承認這個是半開玩笑的……

如果是多邊形或者是有限點集（一回事啦）的話，參見Milo Yip的答案[1]就好。如果是曲線的話，參見他的答案[2]就好，我太弱了懶得點開看了，不過我謹慎懷疑他的那個「曲線」應該是有條件的，要麼就是O(n)複雜度里的n不是曲線的段數。比如，n段n次曲線，組成的東西的複雜程度應該不比n^2個點低，如果他的方法給出平均O(n)的話我是會懷疑的。

當然還有一些奇奇怪怪的邊界情況，比如那個不規則形狀的東西是個IFS分型（Iterated function system）怎麼辦？這時候輸入大小極其小（因為只需要按照IFS分型規則給n個仿射變換出來就行了），不知道O(n)能不能做得到。當然，或許由於IFS的特殊性，會有神奇的解法，有興趣的話你可以試試。

圓心不一定是重心，想像有個桿很細很長的棒棒糖。
然而我不知道應該是什麼……

邊界上任取一點A，搜索邊界點B，計算兩點間距離，當AB距離最大時，確定B的位置，以B為起點搜索邊界點C，取距離BC最大時C點位置。若A，C兩點不重合，以C為起點繼續搜索點D，直到終點位置與起點A重合時停止搜索，最後一次搜索兩點連線做圓的直徑，得到最小直徑覆蓋圓

（1）百度一下最小圓覆蓋
（2）重心法是錯的，比如頂角120度的等腰三角形的重心在底邊的高上，而最小覆蓋圓的圓心在底邊中點，顯然後者的半徑更小。

初步考慮了一下這個問題，我想到的第一個問題就是，這個問題不是就最小長方形問題么？因此我想問下，將問題簡化為求這些點集的最小包圍長方形，通過求得的長方形，計算出圓可以不？

如果是封閉圖形，是不是可以這樣
找圖形內一點，畫一條線，按一個方向旋轉，與圖形邊緣焦點形成線段，最長的做圓

先搞清楚一點，地球是球，你只需要在圖形外面做一個儘可能小的圓即可。

第一次在知乎上回答問題。今天失眠了，在知乎上逛，看到了你的問題挺有趣的，再一想，這個問題也很簡單，山東省的地圖是實際存在的，有他的經緯度，所以在坐標上是一一對應的，所以可以用微積分求得山東省的重心(別告訴我重心不知道怎麼求，若不會求我可以告訴你)，既然重心求出了，兩點間的距離公式求得的最大距離即是最好的半徑