Posted on 2010-07-01 09:56
王之昊 閱讀(1061)
評論(0) 編輯 收藏 引用 所屬分類:
三維幾何 、
隨機(jī)增量
Warehouse Location
最小包圍球，采用隨機(jī)增量的方法。時間復(fù)雜度O(n)。
首先一個點(diǎn)的情況最小包圍球的半徑為0，沒有什么意義。
對于求 n 個點(diǎn)的最小包圍球，假設(shè)這 n 個點(diǎn)分別為 p1,p2, ..,pn。我們可以先求兩個點(diǎn)p1,p2的最小包圍球，再求三個點(diǎn)p1,p2,p3的最小包圍球，總之在求前 k 個點(diǎn)的最小包圍球之前，先求前 k-1 個點(diǎn)的最小包圍球。這里的點(diǎn)是已經(jīng)經(jīng)過隨機(jī)洗牌的，假設(shè)前k個點(diǎn)的最小包圍球是Ck
如果pn被 球Cn-1 所包圍，那么Cn=Cn-1；否則Cn一定經(jīng)過pn，這樣我們知道Cn經(jīng)過的一個點(diǎn)，我們再重復(fù)上面的方法重新去算一遍Cn，結(jié)果要么是直接確定了Cn，要么是增加一個Cn一定經(jīng)過的點(diǎn)。然而如果知道4個Cn經(jīng)過的點(diǎn)，那么這個球也就唯一確定了。