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