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