[科普中國]-最小圓覆蓋

最小圓覆蓋算法可以在線性時間復(fù)雜度內(nèi)求出覆蓋n個點的最小圓。

算法步驟：①首先現(xiàn)將所有點隨機排列1；

②按順序把點一個一個的加入（一步一步的求前i個點的最小覆蓋圓），每加入一個點就進入③；

③如果發(fā)現(xiàn)當前i號點在當前的最小圓的外面，那么說明點i一定在前i個點的最小覆蓋圓邊界上，我們轉(zhuǎn)到④來進一步確定這個圓，否則前i個點的最小覆蓋圓與前i-1個點的最小覆蓋圓是一樣的，則不需要更新，返回②

④此時已經(jīng)確認點i一定在前i個點的最小覆蓋圓的邊界上了，那么我們可以把當前圓的圓心設(shè)為第i個點，半徑為0，然后重新把前i-1個點加入這個圓中（類似上面的步驟，只不過這次我們提前確定了點i在圓上，目的是一步一步求出包含點i的前j個點的最小覆蓋圓），每加入一個點就進入⑤；

⑤如果發(fā)現(xiàn)當前j號點在當前的最小圓的外面，那么說明點j也一定在前j個點（包括i）的最小覆蓋圓邊界上，我們轉(zhuǎn)到⑥來再進一步確定這個圓，否則前j個點（包括i）的最小覆蓋圓與前i-1個點（包括i）的最小覆蓋圓是一樣的，則不需要更新，返回④；

⑥此時已經(jīng)確認點i，j一定在前j個點（包括i）的最小覆蓋圓的邊界上了，那么我們可以把當前圓的圓心設(shè)為第i個點與第j的點連線的中點，半徑為到這兩個點的距離（就是找一個覆蓋這兩個點的最小圓），然后重新把前j-1個點加入這個圓中（還是類似上面的步驟，只不過這次我們提前確定了兩個點在圓上，目的是求出包含點i，j的前k個點的最小覆蓋圓），每加入一個點就進入⑦；

⑦如果發(fā)現(xiàn)當前k號點在當前的最小圓的外面，那么說明點k也一定在前k個點（包括i，j）的最小覆蓋圓邊界上，我們不需要再進一步確定這個圓了（因為三個點能確定一個圓?。?，直接求出這三點共圓，否則前k個點（包括i，j）的最小覆蓋圓與前k-1個點（包括i，j）的最小覆蓋圓是一樣的，則不需要更新。

復(fù)雜度時間復(fù)雜度：O(N)

空間復(fù)雜度：O(N)

復(fù)雜度證明：空間復(fù)雜度顯然，下面來證時間復(fù)雜度。

首先，因為我們已經(jīng)將點打亂順序，所以我們可以認為點是隨機生成的，我們知道，當點完全隨機時，第i個點在前i-1個點的最小覆蓋圓外的幾率是3/i。

本詞條內(nèi)容貢獻者為:

李嘉騫 - 博士 - 同濟大學(xué)