多邊形最短路徑文摘為了計算非凸多邊形表面的最短路徑，我們提出一種算法。這種算法也用來計算多面體的內(nèi)部布局和細(xì)分的多面體表面的任意源點之間的距離，也能用來處理查詢?nèi)我庠袋c和目的點的最短路徑。我們的算法用一種新的偏離常規(guī)的'continuousDijdstra”技術(shù)。我們的算法的時間復(fù)雜度是O(n2)和空間復(fù)雜度Q(n).關(guān)鍵字：最短路徑移動規(guī)劃非凸多邊形單源最短路徑計算幾何計算機器人簡介最近的研究熱點有機器人領(lǐng)域，地形導(dǎo)航，工業(yè)自動化的研究促進(jìn)了運動規(guī)劃。在運動規(guī)劃中一個基本的問題是最短路徑。最短路徑有多個版本。在二維情況下求多邊形的最短路徑問題能夠解決，通過構(gòu)建一個可視化的圖。我們知道的最快的算法有Reif和Storer，時間復(fù)雜度為O(nk+nlogn)，這里n是頂點個數(shù)，k是不想交的簡單多邊形的個數(shù)。某種特殊情況下在兩個空間的情況也有定義最短路徑，時間復(fù)雜度是O(nlogn)。最短路徑問題再三維情況下是NP難題，現(xiàn)在知道只有指數(shù)時間復(fù)雜度算法。在三維情況下的一個特殊狀況是沿著單個多邊形的最短路徑問題。單源最短路徑問題要求在多邊形表面構(gòu)建子多邊形，這樣一個固定點到任何目的點之間的最短路徑才能夠很快得出。單個凸多邊形的單源最短路徑問題首先是Sharir和Schorr研究的。他們的算法事件復(fù)雜度是O(n3logn),這里n是測量多邊形表面邊數(shù)的復(fù)雜度。在建立子多邊形后，最短路徑問題就變成一個點位置問題，最短路徑是從一個固定源點到一個給定查詢點之間的距離，時間復(fù)雜度是O(k+logn)，k是邊在相應(yīng)最短路徑邊緣序列的數(shù)目。Mount提出了一種改進(jìn)的算法，這種算法將運行時間減少到(n2logn)。對于任意的一個非凸多邊形，O’Rourke，Suri，和Booth給出了O(n5)的算法。之后，Mitchell，Mount和Papadimitriou又提出了一種時間復(fù)雜度是O(n2logn)的算法。所有前面的算法可以看作是一個預(yù)處理多邊形通過在多邊形表面建立分支，使在分支區(qū)域上的點有相同的最短路徑邊序列。我們的算法完成相同的任務(wù)。在前面的設(shè)計中用到的一項技術(shù)的實質(zhì)叫做“continuousDijkstra”。Mitchelletal是第一個推廣和鞏固這項技術(shù)的人，并且給它取了個名字“continuousDijkstra”。在這項技術(shù)的一個應(yīng)用中，某些實體(點，邊，面)被看作是圖形的節(jié)點，這些實體到源點得最短距離經(jīng)常引出Dijkstra算法的擴展。為了便于得到實體的最短距離，提出了一種優(yōu)先實體序列。在這里我們提出一種新的算法來計算非凸多邊形表面單源點的最短路徑。我們的算法用一種不同的途徑來實現(xiàn)。它沒有Dijstra算法的特征。同樣，我們也不主張用優(yōu)先序列，實體的擴展在我們的算法中也是不需要運用上面那些從原點的最短距離。我們的算法結(jié)構(gòu)很簡單。這種簡便來自我們對問題看問題的新角度。觀察“一個角度一個分裂”（第三節(jié)）導(dǎo)致順序數(shù)的分支數(shù)量的邊界值上升。然而另一種觀察（第四節(jié)）給出了新的多邊形內(nèi)部布局，這種布局可以看做是雙重的Sharir和Schorr的外部布局。這種內(nèi)部布局的結(jié)果是一次性計算所有的Voronoi圖的面，而不是一次只計算一個面像前面的那種設(shè)計那樣。我們的這種觀察點取得了O（n2）的時間復(fù)雜度。另外，我們也能維持順序書僅僅用了O（n）個節(jié)點。因此取得了最佳的Q（n）空間復(fù)雜度。我們最近的工作進(jìn)展的結(jié)果發(fā)表在這里。以前，Shair和Schorr用O（n2）的空間復(fù)雜度來存儲一個凸多邊形的最短路徑信息。進(jìn)一步取得了O（nlogn）的空間復(fù)雜度來存儲最短路徑信息。對于一個非凸多邊形，O（n2）的空間復(fù)雜度是可以達(dá)到的。但是還沒有發(fā)現(xiàn)比O（n2）更好地結(jié)果。我們有一個方案來存儲最短路徑信息用O（nlogn/logd）的空間復(fù)雜度來支持預(yù)處理查詢用O（dlogn/logd）的時間復(fù)雜度，其中1<d<n，并且d是一個整數(shù)。與此同時，Aronovetal和Aronov，O’Rourke研究凸多邊形內(nèi)部布局，他們被稱為展現(xiàn)多邊形的明星。Aronov和O’Rourke證明了，凸多邊形的內(nèi)部布局不重疊。這個結(jié)果簡化了我們在凸多邊形情況下內(nèi)部布局Voronoi圖的計算。不過我們算法的時間和空間復(fù)雜度并沒有受到他們結(jié)果的影響。這篇文章的剩下部分的組織如下。為了讓大家更加清楚的了解我們的算法，第二節(jié)到第四節(jié)我們的討論范圍限制在凸多邊形的情況。在第二節(jié)，我們回顧了一些初步認(rèn)識多邊形表面最短路徑的知識。在第三節(jié)，我們講述了一種算法來建立n個分支的有序樹。這個算法建立在一個源點到目的地的最短路徑的時間復(fù)雜度為O（n2）和空間復(fù)雜度為Q（n）。在第四節(jié)，詳細(xì)介紹計算內(nèi)部布局和建立細(xì)分。在第五節(jié)，我們運用算法來計算非凸多邊形的情況。第六節(jié)，是對全文的一個總結(jié)。初步認(rèn)識假設(shè)p是一個多邊形，p的表面有一系列面fi，系列邊ei，一系列點vi，一系列角qi。由面的邊組成角，角用來證明重要的最短路徑性質(zhì)，叫做“一角一裂”。n是多邊形的復(fù)雜度，n可以是邊數(shù)，點數(shù)，面數(shù)或者角數(shù)。為了獲得一個不規(guī)則的模型，我們將所有給的多邊形三角面化，同時也將含有源點s的面三角化，所以s變成一個點，正如在Ref做的一樣。這個過程花費了O（n）的時間復(fù)雜度，n是多邊形的邊數(shù)。三角面化后多邊形的復(fù)雜度不變，邊數(shù)還是O（n）。伸展是在研究最短路徑中的一個方法。假設(shè)fl，el，f2，e2，....，fi，ei，f（i+1）....，e（m-1）,fm,是面和邊的序列，ei=fi&f（i+1），fl是邊界含有源點的面。伸展的程序描述如下：F：={f1}；Fori：=1tom-1do在ei附近循環(huán)F直到F,f(i+1)平行，在ei的不同邊F：=F&{ei，f(i+1)}經(jīng)過上面的，所有的面都伸張為一個平面。任何最短路徑n通過這些面都被伸展成一條直線丸(23)我們叫邊序列el,e2,.....,ei是最短路徑序列。Noshortestpathscanpassthrough如電...e8.I'j.I.八J'Lfin-l'inJ'lf'-l-r-L|uf-nrT'.某些邊不是最短路徑序列，沒有最短路徑能夠通過這樣一個序列，如Fig.l.所示。我們能夠通過在每個邊ei源想象一個Iei，源點s的Iei在面fi的平面坐標(biāo)系統(tǒng)中展開，Projei(Iei)，I(ei)在ei上的射影，是一段封閉的線，因此，最短路徑到任何在線上的點p都通過序列e1，e2，....，e(i-1)，并且能夠被展成一條線段(這樣一條理想的路徑就叫做測地線)(Fig.2.2).任何在Projei(Iei)中的點p，我們都能用一條直線來連接I(ei)和p，并且這條線只經(jīng)過邊e1，e2,....，e(i-1)，ej是ej在面fi的展開平面坐標(biāo)系統(tǒng)中的映像。用I(e(i-1))和Proje(i-1)(Ie(i-1))很容易計算出I(ei)和Projei(Iei)oProjei(Iei)是ei和Proje(i-1)(Ie(i-1))陰影在面fi(Fig.3.)的交叉點。如果Projei(Iei)非空，就展開在ei附近的f(i+1)o下面是關(guān)于在一個凸多邊形上的最短路徑的性質(zhì)：1最短路徑最多只能通過每個面一次。因此，一條最短路徑不能通過多于n個面，n是多邊形面的數(shù)量。2兩條最短路徑不能相交，除非在源點或者終點。由于最短路徑不能相交，最短路徑到多邊形的點可以排成一個環(huán)狀根據(jù)從源點發(fā)射的角。脊點是一個從原點s出發(fā)有多于一條最短路徑的點。如果沒有點是脊點，最短路徑到頂點的環(huán)狀順序可以看成是一個除了源點的頂點環(huán)狀順序（這個也可能是一個點）。Fig.2.GeudeyicFig.2.GeudeyicShsdowofI,冬：、PlM|r'Iiuji,當(dāng)一個頂點v是以有k條最短路徑的脊點時，我們可以擴展頂點的環(huán)狀順序，通過添加v的k個副本（包括原始的V），把這些副本排到環(huán)序里面。這樣我們就從到頂點的最短路徑環(huán)序得到了多邊形頂點的一個環(huán)序。序列樹綜合我們前面所講的，一個初步的算法就可以設(shè)計出來了。I'j'1.IjiT'njrijjn^jljnri.我們將一條邊分解成向量邊就像在Ref里面一樣，這樣映像源點就只能在向量邊的左邊（Fig.4.）。下面我們用的邊都是指向量邊除非特殊說明。到一個方向邊的另一邊的面試邊的陰影面。一個面可以是它三條邊的陰影面。我們可以把一個面看作是有三個圖層，每個圖層是一一條邊的一個陰面。下面的算法構(gòu)造一棵順序樹。一個節(jié)點除了根節(jié)點是一個三元組，n（t）=（e，I，PrjI（e）），I是e的映射點，節(jié)點n（t）在邊e上，e是n（t）的邊，n（t）也是PrjI（e）的陰影。算法：root：=s；fors對面的所有邊e插入（。，S，e）作為根節(jié)點的子節(jié)點/*e是含有s的賣弄的一條邊*//*s是三角面化后的一個點*/fori:=1到n/*n是面的數(shù)量*/For在第i層的所有葉子（e，I，ProjI（e））開始展開I從e到rfore’:=AB,CA計算ProjIe（r）如果ProjIe(r)不為空插入(e’,I,ProjIe(r))作為(e,I,ProjIe)的子節(jié)點結(jié)束定理：所有的從s開始的最短序列都包含在算法1中的路徑序列中。證明：構(gòu)造一棵樹后，樹上的每個點都定義了一個含有邊的邊序列，這些邊都是從根節(jié)點到節(jié)點的節(jié)點。對于在面fi上的點p，p包含早節(jié)點D的陰影中，節(jié)點D保證地測線路徑從p到由D定義的邊序列。通過選擇從s到p的最短路徑序列節(jié)點，我們可以為p找到最短路徑。算法1是正確的，因為最短路徑可以被展成一條直線，通過最短路徑的面數(shù)沒有多余n。l-i^,-S,I-'.lIh-jjJillin^,樹可以有指數(shù)數(shù)量的節(jié)點，因為所有的陰影覆蓋了相反角的節(jié)點有在樹中有兩個孩子(Fig.5.).下面來證明陰影覆蓋住相同角的節(jié)點最多有兩個孩子。定理1：三角形ABC的邊CB的兩個點n1，n2的陰影覆蓋住了A，角CAB的頂點，最多有一個點有兩個子節(jié)點，能夠用來定義最短序列。證明：展開I(n1)，I(n2)，CB邊的n1，n2，跟三角形ABC是同面的(Fig.6.)I(n1),I(n2)是展開后源點的映像。如果|I(n1A)|<|I(n2)A|這樣更短的路徑到AB和CA的點就可以充分的靠近A，它是通過代表n1的最短序列的路徑，因此n1的兩個孩子可以用來定義最短序列，并且n2的子節(jié)點能用來定義最多序列。同理，如果I(n1A)|>|I(n2)A|,n1連接n2，n1和n2最多有一個孩子能用來定義最短序列。I'l胃h.I\TfiHf'nr-f-jriffl<lL^'fj'lfAA.根據(jù)定理1,我們只能讓離角最近的節(jié)點n’分叉成兩個子節(jié)點。我們說n’填充了角。如果我們用“一角一裂”在序列樹中，樹的葉子數(shù)目就減少到O(n)，因為在多邊形中有O(n)個角。當(dāng)一片葉子n’=(BC,I(BC),ProjI(BC)(BC)),在三角形ABC面的BC邊上處理過，如果它的陰影不能覆蓋住A，它可以插入唯一的一個孩子。如果它的陰影能夠覆蓋住A，先檢查它能否填充角CAB。如果不能，插入它的唯一的一個孩子。否則，插入它的孩子，然后標(biāo)記角CAB被n’填充。如果n(n)是前面被角CAB填充的節(jié)點，根據(jù)定理1剪掉它的一個孩子，并且刪除子根節(jié)點和孩子。算法21.root：=s；for面s的所有邊e插入(。，s，e)作為根節(jié)點的孩子2fori:=1至Un/*n是面數(shù)*/For第i層得所有葉子n’=(e,I,ProjI(e))開始展開I從e到I(―)/*I(-)與三角形ABC同平面*//*是面e的陰影*/計算Proj(I)(AB)和Proj(I)(CA)/*在AB和CA上的射影*/如果n(r)的陰影覆蓋了A如果n’可以填充角CAB超過n(n)/*n(n)填充了角CAB*/(a)那就去掉n(n)中的一個的兩個孩子那還不能定義一條最短序列，再刪除它的子根節(jié)點和孩子；插入（AB，I（-），Proj（I（-））AB），（CA，I（-），Proj（I（-））CA）作為n（r）的孩子；標(biāo)記角CAB被n’填充；否則/*n’不能填充角*/計算Proj（I（-）e’）/*e’是可能是CA或者AB，無論那條都能定義一條最短序列*/插入（e’,I（-）,Proj（I（-））e’）作為n’de最下面的一個子節(jié)點‘否則/*n（r）的陰影不能覆蓋住A*/e’：=非空的AB或者CA插入（e’,I（-）,Proj（I（-））e’）作為n’的最下面的一個子節(jié)點結(jié)束定理2：所有的從s出發(fā)的最短序列都在算法2中的序列中。證明：通過引理1，在算法2中刪除的節(jié)點不能定義一條最短序列。因此，所有的最短序列都包含在輸出樹中。定理3：算法2的時間復(fù)雜度是O（n2）證明：“一角一裂”的性質(zhì)是在執(zhí)行算法2的時候提出的。因此在算法2中循環(huán)迭代后，樹只有O（n）片葉子。這時，考慮到在生成樹過程花費的時間，跟在步驟a中刪除子樹的不同。因此在循環(huán)迭代后有O（n）片葉子，花費了O（n）時間去生成下一層的樹，當(dāng)我們在生成樹時，允許兩個時間單元來形成每個節(jié)點，一個用來生成一個節(jié)點，另一個留下來（可以看做是節(jié)點上的標(biāo)號）。如果節(jié)點后來被刪除了，這時留下的時間單元就能用了。因此算法2的時間復(fù)雜度是O（n2）。算法2最重要的部分是集成多邊形的最短路徑。為了記錄這些路徑信息，我們引進(jìn)了頂點節(jié)點成為一棵序列樹。一個頂點節(jié)點是一個三角面（e，I，v），v是點，e是邊，I是一個源映像。讓a成為序列樹CB邊的當(dāng)前節(jié)點。a的孩子就形成了。如果a與另一個角CAB的CB邊上的節(jié)點相交，節(jié)點（CB，I（CB）,A）就會作為a的孩子被插入。對于一個頂點節(jié)點（e，I，v），我們用指針去連接點v和邊e。序列樹建好后，到點v的最短路徑就可以形成了，通過檢查連接到v的頂點節(jié)點。到頂點v的最短路徑可以在序列樹中被描繪出來。我們注意到到頂點的最短路徑的信息可以從僅使用O（n）空間的復(fù)雜度2獲得，在生成序列樹的過程中，我們僅需要保持在當(dāng)前序列樹的葉子數(shù)和內(nèi)節(jié)點有不止有一個孩子。在下一階段，如果當(dāng)前樹的葉子只有一個孩子，該葉子將被丟棄并被它的孩子所取代。序列樹因此將生成每一個內(nèi)節(jié)點都擁有不止有一個孩子。對于每一個角度（方向），我們把占據(jù)角度（方向）的節(jié)點存儲起來。如果在同一個角度（方向）有很多的節(jié)點，我們將最遠(yuǎn)的兩個連接節(jié)點存儲起來。對于序列樹的兩個節(jié)點n1和n2,其中n2是n1的一個孩子。我們可以從n1開始描繪出n1到n2的序列邊，在各個角度（方向），對比一下各個角度（方向）存儲的節(jié)點來決定哪一條角邊在邊序中。因此描繪從n1到n2的邊序所用的時間與在邊序中的邊的數(shù)量成正比。為計算第4節(jié)的內(nèi)部布局，我們需用到最短路徑到多面體頂點的循環(huán)規(guī)則。起初，在序列樹中根節(jié)點的孩子可以用循環(huán)規(guī)則來排列。當(dāng)生成序列樹的下一級時，如果我們留意，這個循環(huán)規(guī)則將被保持。當(dāng)這個序列樹被創(chuàng)建，最短路徑到多面體頂點的循環(huán)規(guī)則可以從一個遍歷樹獲得。我們還注意到，如果我們把終點當(dāng)著一個頂點，我們將立即獲得定理2的下一個推論：推論：兩點之間的最短路徑可以由O(n)時間和O(n)空間復(fù)雜度計算得出。注意到如果到頂點v有多條的最短路徑，并且所有的最短路徑都可以通過檢測序列樹的排序(e，I，v)而被找到。細(xì)分計算多面體細(xì)分的主要目的是為了快速檢索存儲的最短路徑信息。計算再次分割的工作曾經(jīng)是通過計算多面體每個面的泰森多邊形法來實現(xiàn)的14,15,23。我們的方案允許我們使用一次泰森多邊形法來求解多面體的所有面數(shù)。首先，我們計算一下多面體內(nèi)部的線路圖，然后我們用泰森多邊形法來計算該線路圖。這兩步都可以用O(n2)時間和O(n)空間復(fù)雜度計算得到。為檢索而存儲最短路徑信息的難點是處理最后的一部分(截面)。4.1.布局一個凸多面體表面的二維布局是由于Sharir和Schorr23削去所有的脊線而獲得。當(dāng)削去所有的脊線之后，多面體的表面可以一個平面上展開。這個布局是一個星狀的多邊形。這個多邊形的邊是一條條的脊線。該多邊形的頂點是多面體中的任一頂點或是脊線上的泰森多邊形頂點。如此一個星狀的布局如下圖7所示。S圖7.外部布局S這里我們給出了一個新的規(guī)劃方法，該方法可以由從源點起到多面體的頂點處削去最短路徑而得到。為了這種使規(guī)劃方法正式，我們定義了一個平面規(guī)劃，一組面數(shù)F如同在一個平面上的F個圖像通過變換次數(shù)T，在平面上將每一個面變換F次。T為保持的形狀，在各個面的連通性中，轉(zhuǎn)換之前，也就是這同一條邊上的兩個不同側(cè)面，在轉(zhuǎn)換之后必有不同的側(cè)邊圖像。我們有以下的定理：定理4：一個多面體的表面將被到頂點最短路徑的多面體所削去，在同一個平面上能夠被設(shè)計出來。證明：我們單獨切去到任一頂點的最短路徑的對面體表面（如圖8），如果到一頂點的最短路徑不僅僅只有一條，我們將切去那個頂點的任一條最短路徑。通過切割，一些面將被分成一塊塊（也可叫做區(qū)域）。畫出這些區(qū)域的一個對偶圖D，把每一塊區(qū)域當(dāng)做對偶圖D的一個頂點（我們?nèi)∮媚切]有因到頂點的最短路徑的多面體而被削去的面，就像一個單獨的區(qū)域包含所有的面）。兩個頂點由一條邊連接，如果相應(yīng)的區(qū)域共享多面體的一條公共（無向）邊，該對偶圖D的邊不會與被削去的到頂點最短路徑的多面體相互交叉。對偶圖D是沒有環(huán)的（非循環(huán)的），因為，如果有一個有環(huán)（循環(huán)）的對偶圖，這個環(huán)將這個多面體的表面切割成兩部分，然后將在多面體的一部分中產(chǎn)生一個沒有源點S的頂點D。因此，從源點S到頂點D的最短路徑將在環(huán)中相交。這與定理相互矛盾。圖8.內(nèi)部布局從一個區(qū)域開始，展開每一塊區(qū)域，且每一塊區(qū)域共享一條公共邊的都將在同一平面L上。由于對偶圖D是沒有環(huán)的（非循環(huán)的），無論我們以從方向展開區(qū)域，我們都將不會返回到相同的區(qū)域中去。因此我們能夠所有的區(qū)域展開到同一個平面上。這個布局的獲得同樣是一個星形的多邊形。多邊形布局中的邊是多面體中從源點到頂點的最短路徑，布局多邊形的頂點是源點的圖像。如此一個多邊形布局如圖8所示。我們必須根據(jù)Sharir和Schorr23的外部布局來調(diào)用布局，最短路徑是由中間發(fā)散出來，也就是源點，向外朝著終點的方向，同時我們必須調(diào)用當(dāng)前這里的內(nèi)部布局，一條從源點到終點向多邊形布局的內(nèi)部區(qū)域行進(jìn)的最短路徑。在一個布局中（任何一個內(nèi)部或外部布局），除源點的多面體頂點，根據(jù)到頂點最短路徑的環(huán)形規(guī)則，能夠被排列到一個環(huán)形規(guī)則中去。如果我們把環(huán)形規(guī)則中毗鄰的兩個頂點用直線段連接起來，這些直線段構(gòu)成一條封閉的曲線。對于每一條直線段，我們定義內(nèi)部的一邊為源圖像。因此這條封閉曲線把多面體的表面分解成兩部分，包含源點的部分叫做北極，另外一部分叫做南極。這條封閉曲線叫做關(guān)于所給源點多面體的赤道。在存儲最短路徑信息時，布局是一個很重要的設(shè)計，特別是那個內(nèi)部布局能夠使我們一次性計算出森泰多邊形的所以面。我們注意到，關(guān)于內(nèi)部布局，Agarwal等人1獨立地做出了相似的觀察值。Aronov和O’Rourke2最近表明一個凸多面體的內(nèi)部布局并不會重疊。在他們的結(jié)果發(fā)表之前，我們把內(nèi)部布局當(dāng)做是它們就是重疊在一起，對于非凸多面體來說因為這是一個不可避免的情況。凸多面體的非重疊性質(zhì)在我們的計劃設(shè)計中并不是一個基本要素，但在凸多面體的情況下它幫助簡化我們的復(fù)雜度。在下面，我們給出了一個為計算內(nèi)部布局而使用序列樹作為輸入值的復(fù)雜度，注意到我們并沒有存儲多面體的邊和多面體中到頂點最短路徑的交集。因此內(nèi)部布局可以被O（n）線段所表示。算法3：遍歷序列樹，獲得布局中的環(huán)形（循環(huán)）規(guī)則；對于環(huán)形（循環(huán)）規(guī)則中每兩個連續(xù)的頂點，從源點開始進(jìn)行計算它們的最短路徑；沿著這兩條路徑切割表面；展開一部分的表面直到兩條路徑在平面L上共面；定理5：算法3用O（n2）時間和O（n）空間復(fù)雜度來計算一個多面體的內(nèi)部布局。證明：因為到頂點的最短路徑被切割且多面體的表面被展開，我們得到內(nèi)部布局。一個遍歷樹，切割面和展開面，采用用O（n2）時間和O（n）空間復(fù)雜度。4.2Voronoi（泰森多邊形）圖和分支構(gòu)建布局之后，在布局中源點S有O（n）個圖像。我們現(xiàn)在計算關(guān)于這些圖像的Voronoi（泰森多邊形）圖。這個布局被Voronoi（泰森多邊形）圖劃分為多個區(qū)域，同一個區(qū)域里的點，與源點S的對應(yīng)圖像比其他的圖像離的更近，并且到源點S的最短路徑經(jīng)過相同的邊序列。南極的內(nèi)部布局，Voronoi（泰森多邊形）圖是一個O（n）邊樹，并且樹中的每一葉子都是多面體的一個頂點（如圖8）23.O（nlogn）時間和O（n）空間復(fù)雜度足夠計算出Voronoi（泰森多邊形）圖22.我們在這里忽略構(gòu)造Voronoi（泰森多邊形）圖的細(xì)節(jié)，因為在下一環(huán)節(jié)中我們將輪廓出Voronoi（泰森多邊形）圖的結(jié)構(gòu)，對于非凸多面體的復(fù)雜情況。定理6：一個多面體的表面分支能夠用O（n）時間復(fù)雜度來計算得出。證明：通過找到多面體中邊的脊線和到頂點最短路徑的交集，一個多面體的表面分支就能夠被得到，當(dāng)把脊線展示在內(nèi)部布局時，便成了Voronoi(泰森多邊形)圖的邊。因此通過在內(nèi)部布局中采集Voronoi(泰森多邊形)圖的邊和到頂點的最短路徑，我們能夠得到分支，并將它們的多面體表面包裝起來。這些操作占用O(n2)時間。因為在分支中有O(n2)個區(qū)域，這就要求有O(n2)個空間來存儲這些分支。注意到我們使用O(n)空間復(fù)雜度來計算這些分支的算法，除那些分支存儲區(qū)域。這些分支能夠被用來回答最短路徑的疑問14,15,23。定理7：在一個多面體的分支被構(gòu)造之后，從源點到質(zhì)疑點之間最短路徑的長度能夠被O(logn)時間復(fù)雜度決定，然而最短路徑能夠通過O(logn+k)時間復(fù)雜度決定，k是穿過最短路徑的邊數(shù)。證明：在多面體的面f上給出一個質(zhì)疑點Q，表示一個位于面f的分支中，我們得到最短路徑到Q的長度，可見參考文獻(xiàn)14,15,23。通過已知的點位置方法8,18O(logn)時間復(fù)雜度可以得出該點的位置。通過回到源點追蹤區(qū)域，可用O(k+logn)時間復(fù)雜度而得出，其中k是穿過最短路徑的邊數(shù)。我們當(dāng)前的工作顯示通過存儲最短路徑信息的O(nlogn/logd)空間復(fù)雜度可以提供O(dlogn/logd)時間復(fù)雜度的判定過程，其中1<dWn,d是一個可調(diào)整的整數(shù)。當(dāng)提供O(dlogn/logd)時間復(fù)雜度的判定過程時，這個結(jié)果確保我們可用O(nlogn/logd)空間復(fù)雜度來滿足我們切割所有的空間的需求。非凸面情況在這一節(jié)我們將討論復(fù)雜情形下的非凸面情況。我們處理非凸面多面體將遵循Mitchell等人的方法14。定理8：一個凸多面體的序列樹能夠用O(n2)時間復(fù)雜度和@(n)空間復(fù)雜度所構(gòu)建。證明：如果一個多面體是非凸的，一條最短路徑穿過多個頂點是可能的14。假設(shè)v是下一個最短路徑從源點S到終點D的頂點。距源點S的最短路徑包含從S到v的最短路徑和從v到D的最短路徑。我們可以把任一頂點v看做是一個初始距離和從S到v最短路徑的長度相等的偽源點。S本身就是一個初始距離為0的偽源點。在序列樹中我們使用兩類節(jié)點。一個節(jié)點是任一頂點節(jié)點，一組(v,5)或一個邊節(jié)點，四維(e,I,ProjIe,&)，其中5是目前已知的從源點S到偽源點v最短距離，I是v的圖像。一個終點D穿過v的最短路徑長度是5+IDII。一個邊節(jié)點可以有至多兩個邊節(jié)點，一個頂點節(jié)點由它的孩子所定。一個頂點節(jié)點有至多兩倍于伴隨邊數(shù)的孩子數(shù)。一半是邊節(jié)點，另一半是頂點節(jié)點。因此，對于非凸面情況來講，“一角一分割”原則需要被稍微改進(jìn)。只有占據(jù)一個角度的邊節(jié)點才能有三個孩子。因為在序列樹中多面體的每個角度最多只能貢獻(xiàn)兩個葉子。多面體所有角度貢獻(xiàn)的序列樹葉子總數(shù)是O(n)。頂點節(jié)點ni=(vi,5i)能有至多2mi個孩子，其中mi是伴隨著vi的邊數(shù)。盡管一個頂點可被多次占據(jù)，對于序列樹中多面體的任一頂點來講，我們至多只需要一個頂點節(jié)點。因此，所有頂點節(jié)點貢獻(xiàn)的序列樹葉子總數(shù)是O(n).所以，在執(zhí)行復(fù)雜度2的任何時間內(nèi)，葉子總數(shù)總是O(n).緊接著就是定理8的正確性。正如凸面情況，序列樹給出了多面體從源點S到所有頂點的最短路徑。在凸面情況，一個脊點被定義為一個點R，從源點出發(fā)不止有一條最短路徑23。這個定義