Smallest Enclosing Circle 最小覆蓋圓
最小覆蓋圓 ：平面上給定 n 個點，求出能包含所有點且半徑最小的圓。
最小覆蓋圓可以使用 Randomized Incremental Construction 在O(n)時間內求得。該演算法的想法是，從一個點 (半徑為0的圓) 出發，每次多考慮一個新的點時，伺機調整圓的半徑與圓心，使其成為能夠容納當前所有點的最小覆蓋圓。這裡有個 Buffalo大學的slides 有很詳盡的解釋過程。這篇文章是個人的學習筆記，穿插一些最小覆蓋圓性質的小證明。
性質一：最小覆蓋圓是唯一的
證明用反證法：假設存在兩個最小覆蓋圓
c1跟c2皆包含點p[1..n]。由於c1跟c2包含相同的點群，該點群必存在於兩圓的交集區域上。我們可以利用該交集區域製作出一個半徑更小的c3依然包含p[1..n]，這導致c1跟c2不是最小覆蓋圓，與假設矛盾。所以最小覆蓋圓是唯一的。
性質二：最小覆蓋圓的邊界上至少有兩個點，且任兩點之間的弧必小於 180度。
證明是先建構一個包含所有點的圓，然後逐漸縮小到無可再小。跟據性質一，這個無可再小的圓就是最小覆蓋圓。
1. 如果邊界上沒有點的話，我們可以縮小圓的半徑，直到邊界撞上一個點。如下面左圖點H。
2. 如果只有一個點在邊界，我們可以藉由讓圓心往該點移動而縮小圓半徑 ，直到撞上第二點。如下面右圖圓心 A 往點 H 移動。
3. 如果邊界上有兩個點的話，此兩點必需在圓直徑的兩端(兩極) 。否則我們可以藉由讓圓心向兩點的中點移動以縮小半徑，直到兩點處於兩極，或是邊界撞上第三點。
4. 如果圓上有大於等於三個點，但是存在弧大於180度的話，那我們可以藉由讓圓心向弧相反方向移動來縮小半徑，直到這個弧小於180度，或是撞上其它點把弧切斷。
TODO: 補圖
算法過程
讓p[1..n]代表 n 個點，c[i-1] 是包含了點 p[1...i-1]的最小覆蓋圓。當考慮一個新點 p[i] 時，判斷 p[i]是否在當前 c[i-1]外。如果在圓內的話代表無需更新，可以略過；否則必需調整最小覆蓋圓的圓心與半徑使其可以包容新的點。新的最小覆蓋圓 c[i]包含點 p[1..i] 的最小覆蓋圓而且p[i]會在圓 c[i] 的邊界上。
性質三：
p[i]不在c[i-1]內，則p[i]一定會在c[i]邊界當
p[i]在c[i-1]外面時，我們可以把c[i-1]的半徑擴大到直到包含p[i]，此時的圓會包含所有點，但只有一個點p[i]在邊界上。根據性質二.2，我們可以逐漸縮小圓的半徑直到成為最小覆蓋圓c[i]，在縮小的過程中p[i]一直都會落在邊界上。也可以用反證法證明：假設
c[i]為包含p[1..i]的最小覆蓋圓，且p[i]不在邊界上。由定理一我們知道，這個最小覆蓋圓c[i]必有其它點在邊界上，這些點限制住了c[i]使其無可再小。當把p[i]從圓內移除時，我們無法再進一步縮小該圓。而此時的c[i]跟c[i-1]一樣都是只包含了點p[1..i-1]的最小覆蓋圓。由定理二得知可知包含了點p[1..i-1]的最小覆蓋圓是唯一的，這表示這兩個圓其實相同：c[i] == c[i-1]。這跟p[i]必需要在c[i-1]外面的假設矛盾。
以上圖為例子，目前進行到
p[7]而p[7]不在c[6]內。假設更新後的c[7]在邊界上不包含p[7]，而是p[1],p[3],p[6]這三點，那麼當我們移除p[7]後會得到跟c[6]一樣的最小覆蓋圓，這是不可能的，因為照假設c[6]並不含p[7]
更新後的圓c[i]要滿足兩個條件：
1.c[i] 包含 p[1..i]
2.p[i]在圓 c[i] 邊界上
相當於一個子問題：”如何求出邊界上包含某一個特定點的最小覆蓋圓？”
我們把這個最小覆蓋圓叫d以跟母問題的圓c區分。d[j]代表包含p[1..j]且在邊界上有p[i]的最小覆蓋圓。一開始d只有p[i]一個點，我們可以做一個以p[i]為圓心，半徑為0的圓。接著一個一個重新加入點p[1], p[2]一直到p[i-1]。在加入的過程中，如果有點p[j]落在圓外，我們就更新圓 d。更新完後的最小覆蓋圓d[j]必需同時滿足三個條件：
1.d[j] 包含 p[1..j] (j<i)跟 p[i]
2.p[i]在圓 d[j] 邊界上
3.p[j]在圓 d[j] 邊界上
證明可以利用性質二.3，有空的話再補完。
於是我們有了個子問題的子問題：”如何求出邊界上包含某兩個特定點的最小覆蓋圓？”
依樣畫葫蘆，重新建構一個最小覆蓋圓e，代表包含p[1..k]且在邊界上有p[i]跟p[j]的最小覆蓋圓。e一開始以p[i]和p[j]為兩極做圓：圓心為兩點的中點，半徑為兩點距離之一半。接個重新一個一個加入p[1], p[2]直到p[j-1]，中間任何點p[k]在圓外的話就更新e[k]，e[k]滿足：
1.e[k] 包含 p[1..k] (k < j)跟 p[i] 還有 p[j]
2.p[i]在圓e[k]邊界上
3.p[j]在圓e[k]邊界上
4.p[k]在圓e[k]邊界上
其實條件 2. 3. 4. 三個點p[i]、p[j]與p[k]就可以決定一個圓了，三點外接圓請參考wiki 公式。
這裡我有個困惑：為什麼p[i],p[j], p[k]的外接圓 e[k] 肯定能夠包含之前的點p[1..k-1]呢？有沒有可能有某個舊點p[m]反而跳到 e[k] 外面了？
雖然可以用類似的反證法證明，但是一張圖可以給我們一個更直觀的解釋。我使用了一個叫geogebra 的線上幾何作圖神器說服了自己。請看一下例子：
設有個最小覆蓋圓包含了點 ABCDE。有個新的點F在圓外，我們想做一個新的最小覆蓋圓，而且點A跟點F一定在邊界上。我們先以點A和點F為兩極做一個紅色的圓。
注意到弦AF把原本圓分成了兩邊，其中一邊的點總是會在紅圓內。也就是說，有可能出界的點一定在另一邊。在這個例子中，右邊的點像是點C是一定在紅圓內，接下來只考慮弦左邊的點就行了。很清楚點B與點D不在圓內，我們需要把它們加進去。
接著把點B加入，以點AFB作外接圓。點D依然在圓外，革命尚未成功，同志仍需努力。注意在加入點B後，之前在舊圓內的點C與點E依然在新圓內。
再把點D加入考慮，利用點AFD三點再作外接圓，終於所有的點都被包含了。圓上有三個點，而且沒有弧大於 180 度。最小覆蓋圓get！同樣的，之前在舊圓內的點B點C點E依然在新圓內。
注意到每次我們做新外接圓時，圓心固定只會朝左邊移動，而且圓的半徑會不斷擴大。這個過程會進行到把左半邊的點全吃了為止。
回到問題：是什麼神秘力量使得我們做新外接圓時，舊的點依然會在新圓內？如果我們把圓看成兩部份：在弦AF左半邊的割與在右邊的割。當圓心往左邊移動時，左半邊的割會變大，而且包含舊圓的割(比較一下紅實線與紅虛線)。這保證了在弦AF左半邊的點 (BDE)，原本在舊圓內的話也一定在新圓內。
那右半邊的 (C)呢？當圓心往左移動時，新圓右半邊的割會變小，比較一下紅實線與紅虛線即可得知。然而，我們完全不需要擔心右半割的縮小會讓我損失任何點，因為就算最極端的情況下(右半割最小)，這個外接圓還是能夠包含所有在原本最小覆蓋圓上的點，不管左半邊還是右半邊。
也就是說，當我們固定兩個點建構最小覆蓋圓時，只要針點每個界外的點求一次三點外接圓即可。無需擔心只前的點跑到圓外。
到了這邊，疑惑算是解決了。整個算法過程重新整理如下
0. 把最小覆蓋圓隨便定在某個點，半徑0
1. 一個一個加入點. 加完了就結束
2. 如果點i在圓內，回到 1. (略過)
否則到 3.
3. 以點i為圓心做半徑為0的圓
4. 把前i-1個點一個一個加進去，加完了回到 1.
5. 如果某點j在圓內，回到4. (略過)
否則到 6.
6. 以點i與點j為兩極做圓，去7.
7. 把前j-1個點一個一個加進去，加完了回到 4.
8. 如果某點k在圓內，回到7. (略過)
9. 否則做三點ijk外接圓，回到7.關於時間複雜度的證明可以參考commonc的博客，總體時間複雜度是O(n)。需要強調的是點的排序必需是隨機的，才能保證每個點的平均更新時間複雜度是 O(1)。
最後，代碼：