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

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

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

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

4、，那么連接A2A4，并且刪除與A2A4相交的邊。設(shè)A2A4為新產(chǎn)生的正切線。A1A2A3A5A6A4直線L14相交的邊新確定的正切線A1A2A3A5A6A4Voronoi圖的構(gòu)造重復(fù)上述步驟，我們就能合并兩個(gè)點(diǎn)集的角最優(yōu)三角剖分。 這樣，依照該方案，我們就能構(gòu)造出來點(diǎn)集S的角最優(yōu)三角剖分了。 這個(gè)三角剖分的直線對偶圖就是點(diǎn)集S的Voronoi圖。Voronoi圖的構(gòu)造T(N)=2T(N/2)+O(N)求解含有n個(gè)點(diǎn)的點(diǎn)集的角最優(yōu)三角剖分求解含有n/2個(gè)點(diǎn)的點(diǎn)集的角最優(yōu)三角剖分合并兩個(gè)點(diǎn)集的角最優(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平面上有一個(gè)矩形，在矩形內(nèi)有一些點(diǎn)，請你求得矩形內(nèi)另一個(gè)點(diǎn)，該點(diǎn)離與它最近的已知點(diǎn)最遠(yuǎn)（點(diǎn)的個(gè)數(shù)=1000）。BACDVoronoi圖的在信息學(xué)中的應(yīng)用思路一：大家可能很容易想到用枚舉法情況一：過三點(diǎn)的圓的圓心情況二：兩點(diǎn)中垂線與矩形的邊的交點(diǎn)BA所求點(diǎn)CBAC所求點(diǎn)DDVoronoi圖的在信息學(xué)中的應(yīng)用根據(jù)剛才分析的兩種情況，我們可以構(gòu)造兩種方案。第一種方案針對所求點(diǎn)為過三個(gè)點(diǎn)的圓的圓心的狀態(tài)，我們枚舉三個(gè)點(diǎn)，求出它們組成的三角形的外心和半徑，然后枚舉其它的點(diǎn)，看它們是不是在這個(gè)圓中。第二種方案是枚

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

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

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

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

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