最小圓覆蓋

最小圓覆蓋算法可以線上性時間複雜度內求出覆蓋n個點的最小圓。

算法步驟:

①首先現將所有點隨機排列 ;②按順序把點一個一個的加入(一步一步的求前i個點的最小覆蓋圓),每加入一個點就進入③;③如果發現當前i號點在當前的最小圓的外面,那么說明點i一定在前i個點的最小覆蓋圓邊界上,我們轉到④來進一步確定這個圓,否則前i個點的最小覆蓋圓與前i-1個點的最小覆蓋圓是一樣的,則不需要更新,返回②④此時已經確認點i一定在前i個點的最小覆蓋圓的邊界上了,那么我們可以把當前圓的圓心設為第i個點,半徑為0,然後重新把前i-1個點加入這個圓中(類似上面的步驟,只不過這次我們提前確定了點i在圓上,目的是一步一步求出包含點i的前j個點的最小覆蓋圓),每加入一個點就進入⑤;⑤如果發現當前j號點在當前的最小圓的外面,那么說明點j也一定在前j個點(包括i)的最小覆蓋圓邊界上,我們轉到⑥來再進一步確定這個圓,否則前j個點(包括i)的最小覆蓋圓與前i-1個點(包括i)的最小覆蓋圓是一樣的,則不需要更新,返回④;⑥此時已經確認點i,j一定在前j個點(包括i)的最小覆蓋圓的邊界上了,那么我們可以把當前圓的圓心設為第i個點與第j的點連線的中點,半徑為到這兩個點的距離(就是找一個覆蓋這兩個點的最小圓),然後重新把前j-1個點加入這個圓中(還是類似上面的步驟,只不過這次我們提前確定了兩個點在圓上,目的是求出包含點i,j的前k個點的最小覆蓋圓),每加入一個點就進入⑦;⑦如果發現當前k號點在當前的最小圓的外面,那么說明點k也一定在前k個點(包括i,j)的最小覆蓋圓邊界上,我們不需要再進一步確定這個圓了(因為三個點能確定一個圓!),直接求出這三點共圓,否則前k個點(包括i,j)的最小覆蓋圓與前k-1個點(包括i,j)的最小覆蓋圓是一樣的,則不需要更新。

複雜度

時間複雜度:O(N)

空間複雜度:O(N)

複雜度證明:空間複雜度顯然,下面來證時間複雜度。

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

相關詞條

相關搜尋

熱門詞條

聯絡我們