淺析平面Voronoi圖的構(gòu)造及應(yīng)用

1、引言： 在計算幾何這一領(lǐng)域中，Voronoi圖是僅次于凸殼的一個重要的幾何結(jié)構(gòu)。這是由于Voronoi圖在求解點集或其他幾何對象與距離有關(guān)的問題時起重要作用。 常見的問題包括誰離誰最近，誰離誰最遠，等等?，F(xiàn)在，讓我們大家首先來了解一下Voronoi圖的定義！Voronoi圖的定義設(shè)P1,P2是平面上的兩個點，L是的它們的中垂線，L將平面分成兩部分半平面L1和半平面L2，在L1內(nèi)的點P具有特性|PP1|PP2|，即位于Ll內(nèi)的點比平面中其他點更接近點P1 ，我們記半平面H(P1, P2)= L1 ，同理半平面H(P2, P1)= L2 。 直線LP1P2平面L1平面L2PVoronoi圖的定義

2、對于平面上n個點的點集S,定義V(Pi)=H(Pi,Pj)，即V(Pi)表示比其他點更接近Pi的點的軌跡是n-1個半平面的交集，它是一個不多于n-1條邊的凸多邊形區(qū)域，稱為關(guān)聯(lián)于Pi的Voronoi多邊形或關(guān)聯(lián)于Pi的Voronoi多邊形域。 pin=6時的一種V(pi) 位于多邊形V(pi)內(nèi)的任意一個點P滿足|PPi|PPj|(ij)pPjVoronoi圖的定義 對于S中的每個點都可以 作一個Voronoi多邊形，這樣n個Voronoi多邊形組成的圖稱為Voronoi圖，記為Vor(S)。n=6時的Vor(S)Voronoi圖的構(gòu)造傳統(tǒng)的構(gòu)造方法分治法構(gòu)造Delaunay三角剖分法編寫麻煩

3、難于理解編寫容易易于理解O(N log N)Voronoi圖的構(gòu)造 用分治法構(gòu)造角最優(yōu)三角剖分，首先要對點集依照X坐標排序。如果點集內(nèi)點的個數(shù)小于等于三，那么可以直接構(gòu)造，否則將點集拆分成為兩個含點數(shù)目近似的點集進行構(gòu)造，最后合并這兩個點集。點集內(nèi)含點個數(shù)為2的情況點集內(nèi)含點個數(shù)為3的情況合并兩個子點集的角最優(yōu)三角剖分首先，求解兩個點集的凸包的最下方最下方的正切線,并連接兩端點。接下來，如圖所示，A1A4為兩個凸包的正切線，求出它們的中垂線L14。然后找到L14與A1(或A4)相關(guān)聯(lián)的邊中，中垂線與L14有交點的邊，如果有多個邊，那么選擇交點Y坐標最小的點所關(guān)聯(lián)邊。如圖所示，選擇的邊為A1A2

4、，那么連接A2A4，并且刪除與A2A4相交的邊。設(shè)A2A4為新產(chǎn)生的正切線。A1A2A3A5A6A4直線L14相交的邊新確定的正切線A1A2A3A5A6A4Voronoi圖的構(gòu)造重復(fù)上述步驟，我們就能合并兩個點集的角最優(yōu)三角剖分。 這樣，依照該方案，我們就能構(gòu)造出來點集S的角最優(yōu)三角剖分了。 這個三角剖分的直線對偶圖就是點集S的Voronoi圖。Voronoi圖的構(gòu)造T(N)=2T(N/2)+O(N)求解含有n個點的點集的角最優(yōu)三角剖分求解含有n/2個點的點集的角最優(yōu)三角剖分合并兩個點集的角最優(yōu)三角剖分O(NlogN)Voronoi圖的在信息學(xué)中的應(yīng)用例3.Fat Man例1.Run Away

5、例2.Voronoi圖與平面MST問題Voronoi圖的在信息學(xué)中的應(yīng)用例1.Run Away平面上有一個矩形，在矩形內(nèi)有一些點，請你求得矩形內(nèi)另一個點，該點離與它最近的已知點最遠（點的個數(shù)=1000）。BACDVoronoi圖的在信息學(xué)中的應(yīng)用思路一：大家可能很容易想到用枚舉法情況一：過三點的圓的圓心情況二：兩點中垂線與矩形的邊的交點BA所求點CBAC所求點DDVoronoi圖的在信息學(xué)中的應(yīng)用根據(jù)剛才分析的兩種情況，我們可以構(gòu)造兩種方案。第一種方案針對所求點為過三個點的圓的圓心的狀態(tài)，我們枚舉三個點，求出它們組成的三角形的外心和半徑，然后枚舉其它的點，看它們是不是在這個圓中。第二種方案是枚

6、舉兩個點的中垂線，求出中垂線與矩形的交點，然后根據(jù)這三個點來計算最遠位置，進行判斷。 它的時間復(fù)雜度：O(n4)Voronoi圖的在信息學(xué)中的應(yīng)用思路二：Voronoi圖 首先介紹一個Voronoi圖的性質(zhì)：設(shè)性質(zhì)：設(shè)v是是Vor(S)的頂點，則圓的頂點，則圓C(v)內(nèi)不含內(nèi)不含S的其他點。的其他點。根據(jù)這個性質(zhì)我們很容易想到用Voronoi圖來解決問題，方法如下：步1.計算點集S的Voronoi圖Vor(S)。步2.計算點集S的凸殼CH(S)。設(shè)得到的圓最大半徑Rmax =0。 步3.枚舉每個Voronoi點v,如果v在矩形內(nèi)部，計算v為圓心的圓的半徑并且修改Rmax 。 步4.枚舉枚個CH

7、(S)中的邊e，求出e的中垂線與矩形的交點v，計算v到邊e兩端點的距離，并且修改Rmax。Voronoi圖與平面MST問題例2.平面MST問題給定平面上的點集S，求出連接S中所有點的最小長度的樹，并且要求最小生成樹的結(jié)點恰好是S中的點。Voronoi圖與平面MST問題 傳統(tǒng)的求最小生成樹的方法是貪心法，要是純粹使用貪心法求平面最小生成樹，我們所作的程序時間復(fù)雜度至少為：O(n2)有沒有更快的方法呢？當然有!用Voronoi圖。Voronoi圖與平面MST問題我們都知道Voronoi圖的對偶圖是點集的角最優(yōu)三角剖分，我們把這個三角剖分中的邊組成的集合叫做DT(S). 那么，我們可以得出這樣一個定

8、理：最小生成樹最小生成樹MST是是角最優(yōu)角最優(yōu)三角剖分三角剖分DT(S)的一個子集的一個子集關(guān)于定理的證明 也就是說，具有直徑ab的圓周上或圓內(nèi)必有S中的點，假設(shè)c在該圓周上或者圓內(nèi)，那么|ac|ab|，并且|bc|ab|。那么，我們刪除ab，把樹T分成Ta和Tb兩部分，不妨假設(shè)cTa，那么我們添加邊cb，可以合并成新的樹，并且的總長度小于T，因此包含ab的樹長度不可能是最小的。所以必然MSTDT(S) 證明： 假設(shè)存在一條邊abDT(S)，則由三角剖分的定理可以知道過a,b有一個空圓。因此如果ab不屬于DT(S)，那么過a,b的圓不可能是空的。abcTaTbVoronoi圖與平面MST問題

9、根據(jù)這個條件，我們可以得到一個新的方案，構(gòu)造角最優(yōu)三角剖分，然后計算最小生成樹，總的時間復(fù)雜度是O(n log n)。 可能大家會問這樣一個問題：我想告訴大家！Voronoi圖不僅能快速解決距離問題除了距離問題,Voronoi圖還有什么用呢?Voronoi圖還可以擴寬我們的解題思路Voronoi圖拓寬解題思路例3.Fat Man 在超市走廊上兩邊都是墻，中間有一些障礙物，這些障礙物都是一些很小的半徑可以忽略的點，你是一個胖子，可以將你的抽象成一個圓柱?，F(xiàn)在你要從走廊的一頭走到另一頭。請問你最大的直徑是多少？（走廊長L,寬W）問題分析： 剛開始拿到題目可能會手足無措，如果只是知道平面上的一些點，

10、我們很難確定從走廊一頭到另一頭的路線，也很難運用枚舉等方法來解決問題。但是，當你學(xué)了Voronoi圖，情況就不一樣了！Voronoi圖拓寬解題思路首先我們建立Voronoi圖，顯然一個人如果想穿過這些障礙物，那么走Voronoi邊才是最佳的，因為如果不走Voronoi邊，必然會使你的圓心進入一個Voronoi多邊形內(nèi)，這將使人更靠近一個障礙物，因而會減少人的半徑。所以最佳路線必定由一些Voronoi邊組成。原來障礙點Voronoi圖拓寬解題思路接下來，由于人還可以從走廊邊與障礙物之間通過，那么對于每一個障礙點(x,y)我們可以在走廊壁上增加障礙點(x,0),(x,W),一共增加2n個障礙點。另外在走廊開始和盡頭增加四個障礙點（-W,0），（-W,W），（L+W,0），（L+W,W）這四個點與其它點之間距離不小與W，這