計算幾何第四周：維諾圖

本周目標：對空間進行剖分，然後對這個幾何體進行探究。

1、Terminologies

• 幾個概念

基點Site：具有一些幾何意義的點

細胞Cell：這個Cell中的任何一個點到Cell中基點中的距離都是最近的，離其他Site比離內部Site的距離都要遠。

Cell的劃分：基點Site與其它的n-1個點所對應的那個平分線所確定的那個離它更近的那個半平面。把所有這些半平面公共的交集求出來就是這個cell.

因此每個Cell都是凸的，圖中一定會有一些Cell是無界的

在本課程中只討論二維平面上的Voronoi圖，並且我們存儲Voronoi圖時只需要存儲點和邊界信息。

Voronoi圖中包括Voronoi點（線段與線段之間的交點）、線段Segment、射線Ray或直線，這些線都被稱為Voronoi edge。

2、Properties

（1）非空性：每個Site都擁有一個非空的Site

（2）空圓性：在任何一個Site所對應的Cell中，任何一個點以這個點為圓心，以到這個Site的距離為半徑的圓必然是空的。

這裡的空指的是：圓其中它的內部不包含任何的Site

空圓的另一種形式：點x位於Vertex Edge上，x處於幾個Cell的公共交上，那麼x到這些Cell對應的Site的距離都是相等的，以x為圓心以這個距離為半徑做出來的圓也是空圓。這個空圓也是最大的。

辨析兩個概念：disk是實心的包括內部的整個部分，Circle是一個圓環，只考慮它的邊界。

討論：以一個x為圓心做出的空圓的圓環上最多會有幾個Site？（度數為幾）

①、如果x在Cell內部，那麼它一定是以到該Cell內部的Site為距離作圓，因此只會有1個，度為1。

②、如果x在一條邊界上（不在Voronoi Vertex處），那麼就至少有兩個Site是最近鄰，度至少為2

③、如果x在一個Voronoi Vertex上，那麼它是多少個Cell的公共交處那麼就有多少度。度至少為3。

但是多個Site共圓的情況是一種退化情況，本課程不考慮這個，因此我們在這裡認為如果是在Voronoi Vertex上的點那麼它的度數就為3。

3、Comlexity

為了對Voronoi圖進行複雜性的討論，我們將那些射線強行指向一個無窮遠的點，那麼此時的Voronoi圖就是一個連通圖。

那麼此時Voronoi圖頂點的數目大致在O(2n-4)的範圍，邊大致在O(3n-6)的範圍。無論是頂點還是邊，都是線性的。

證明：令D是Voronoi圖中所有的Cell（即面face）的周長的總和。3f≤D=2e。引入歐拉公式v-e+f-c=1。c是連通域。在Voronoi圖裡連通域c=1。將這兩個公式聯立可以得到頂點數目與邊的數目都與n個Site成線性關係。

4、Representation

我們可以用計算機高效的表示以Voronoi圖為代表的子區域剖分的幾何結構。

平面圖嵌入：可為圖中的每個頂點安排一個具體的位置，並且能保證它們之間的那些連邊可以畫在這個平面上，且互相 不會再內部相交。

subdivision（子區域剖分）：將平面圖所依附的平面這個空間做一個氣的剖分，把它剖分成一個個類似於Voronoi圖的單元部分。如此劃分出來的一個個單元格稱之為face。（對於Voronoi圖而言face就是Cell）

face與face之間的關係：它們聯合在一起能夠將整個平面覆蓋住；任何兩張face在內部都不會有交。

Voronoi圖是subdivision的一個特例。

Fary Theorem：如果能將一幅圖用一種曲線形式畫在平面上的話，那麼也必然能夠以這種完全使用直線的方式把它花在平面上。如下圖

對於一個Voronoi圖，我們不僅要存儲每個Vertex，每條edge，每個Cell，還需要存儲一些點與邊與面之間的關聯關係，這些關聯關係的incidence需要記錄下來。另外，我們可能還需要對圖進行某種遍歷。為此，我們藉助DCEL結構來進行操作。

5、DCEL

下面是DCEL的一系列數據結構

• 邊表

邊分解：將subdivision中連接於以任何兩個頂點中之間的一條無向邊拆解成一對有向邊，這對邊是彼此共存，又叫做twin edges。其中一半邊叫half edge。我們用edge list邊表來記錄拆分出來的這一系列半邊。

Half-edge的數據結構組成：id，twin邊，半邊的起始頂點ori，這條邊參與圍成的面inc（半邊的左側為內側，記錄這個內側邊），半邊的前驅pred和後繼succ。

這裡的前驅和後繼是順著在這個面里的，不能夠一下子跳到另一個面去

• 點表

頂點的數據結構：id，坐標x,y，第一條向外發出的關聯的邊inc。

• 面表

face的數據結構：id，一條incident half-edge(inc)（這個inc就是指一個面做遍歷的時候的起始邊）

• 例子

如圖所示，我們給定一個face f後，就可以利用其中的信息找到它的一條邊，然後通過前驅後繼即可遍歷這個面圍成的邊。如果要得到旁邊的面，那麼通過twin的信息可以翻到另一個面去，它在另一個面也會有相應的前驅後繼。

6、Hardness

對於一般意義上的Voronoi圖：一維的Voronoi圖構造的時間複雜度通過sorting問題來進行reduction。

sorting的輸入是一系列的數，可以轉化為一維Voronoi圖中一系列的點在數軸上。然後我們要將Voronoi圖一系列的點進行排序，並把它的輸出轉化為sorting的輸出。輸入是數軸上的藍色的點，然後要將這些點對應的Voronoi圖構造出來。而構造出來的Voronoi圖的點就是圖中一系列紅色的點。這些紅色的點是兩個藍色點的中點。這樣我們得到了Voronoi圖的一維的答案，然後要將這些答案轉化成排序問題的輸出。我們可以通過一次線性掃描，得到第一個0號點的位置，因為知道了紅1是藍0和藍1的中點，那麼必然知道這個中點的距離，那麼可以通過藍0和紅1知道藍1的位置，如此類推，就會得到之前藍色輸入的點的順序，也就規約到了sorting上。

因為Voronoi圖構造可以規約到sorting，那麼這個問題的下界就是O(nlogn)

對於二維的Voronoi圖，也可以規約到sorting上。

如圖所示，我們輸入了n個未排序的數，我們的任務是將這n個數映射到一個單位元的圓周上。然後這n個點就是二維Voronoi圖在平面上的一個輸入點集。再用二維Voronoi圖的演算法把輸出構造出來。這個Voronoi圖只有唯一一個vertex就位於這個圓的中心x，有多少個點，就有多少條邊，每一條Voronoi邊都是在圓周上相鄰某一對點的平分線。對於這個Voronoi圖的輸出，我們只要知道其中一個點，就可以確定它的Cell，然後通過數據結構里存儲的信息可以將這個圖遍歷出來，也就得到了Sorting的排序。

因此二維的Voronoi圖的構造的下界也是O(nlogn)

然而上圖是一個退化的Voronoi圖，對於非退化一般性的Voronoi圖而言，也可以設計這樣一個reduction。

如圖所示，我們用一個拋物線來代替圓弧。將輸入的點映射到一個拋物線上。然後可以通過簡單的操作在線性時間內找到起點，通過一次一次的flip逐一將所有點枚舉出來，那麼就將輸出映射回sorting的輸出。

因此確鑿明確的知道2維Voronoi圖的問題複雜度下界不會低於O(nlogn)

7、Sorted Sets

討論：如果在給定一些附加條件後，Voronoi圖的難度是否會降低？例如在某些時候我們的輸入子集是蘊含著一些排序的信息，像凸包那樣的問題就可以降低維度，那麼Voronoi圖是否也可以降低難度？

結論：即使輸入的點是按照高度的次序由低到高給出來的，我們依然不能使Voronoi圖這個問題從下界意義上講的效率有絲毫的改進。

解釋：凸包和Voronoi圖的結構其實是有本質區別的。凸包的在本質上是一種Combinatorial structures組合結構，而Voronoi圖本質上是一種geometric structures幾何結構。這二者的區別凸包在仿射變換下具有不變性，即雖然形狀發生了變化，但它的極點和非極點以及極點之間的連接關係是不會發生絲毫的變化的，它的拓撲結構是保持的。

而Voronoi圖在經過仿射變換後經常會發生拓撲結構的改變。

如圖所示是第一個圖先壓縮再拉伸，Voronoi圖的拓撲結構發生了本質上的變化。

發生這個的原因是因為Voronoi圖是依賴於距離，如果是發生與距離有關的改變，那麼就會對它的拓撲結構造成影響。

8、VD_sorted

考慮一個特例：Voronoi圖給出的輸入是在某種意義下有序。

ε-closeness問題：每次輸入n個實數以及一個ε的正數，問在所有這些數中，是否存在兩個它們的間距是不超過ε的。這個問題的複雜度是O(nlogn)

接下來要做的就是VD_sorted這個問題規約到ε-closeness問題上去。

Lifting Transform：對於輸入的一系列的點，在ε的高度區間內， 按照輸入的次序把每個點拔高到對應的區間上。如下圖

這個對應的公式是：

接下來要針對一組任意的輸入調用任何的包括優化的Voronoi圖演算法，去構造出它對應的Voronoi圖。（構造是指要得到例如表示為一個DCEL結構的Voronoi圖）。這種情況下我們可以依次枚舉出與x軸相交的所有的那些cell。接下來將這些Site的點在投影回x軸，其實就是一開始ε-closeness的輸入。

下面分兩種情況討論，無論哪種情況我們都可以得到ε-closeness的答案。區分的準則是這裡的每一個site在經過投影之後回到當初那個點是否就位於提升後的這個site所對應的Voronoi圖中的那個cell中。

如圖所示，1號點和2號點是滿足要求的，其他則不滿足。

Case A：Yes 所有的點都無一例外的落在自己所對應的Cell中。

那麼就可以得到所有的Cell的次序和它對應的site的次序。這種情況下我們就可以得到所有輸入點排序的結果。知道了這些點的排序那麼也就很容易知道相鄰點之間的間隙，而所有這些相鄰點間隙中的最小者就是MinGap，有了它就可以回答ε-closeness這個問題了。

Case B：其他情況，有點不落在自己對應的Cell中。

如圖所示，I點投影下來的i點就並不落在Cell I中。那麼連接i點和它所落在的Cell J里，再加上J的投影點j構成了一個直角三角形。我們可以快速得到ij<iJ<Ii<ε，那麼在整個的輸入的那些實數中，至少存在i和j兩個實數它們的間距是小於ε的。也就是說這種情情況下ε-closeness問題的答案是Yes。

綜上所述，我們只要將ε-closeness問題轉化為VD_sorted這個問題，那麼無論是哪種情況都可以反過來根據VD_sorted問題的輸出順利的得到ε-closeness答案，從而完成歸約。這就意味著VD_sorted這個問題的難度依然是O(nlogn)。

9、Naive_Construction

一個最直接最簡單的方法：一個Cell一個Cell去構造。對於單個Cell構造就是按照定義找出這個Site與其他Site的平分線並且求交，得到的包含Site的封閉的平面就是一個Cell。

這個演算法複雜度在找平分線求交時會有n2的難度，另外還有n個Cell，最後會高達O(n3）

10、Incremental Construction

Incremental algorithm：演算法核心是如何從一個規模為k-1的Voronoi圖通過引入一個新的site構造出規模為k的Voronoi圖。

演算法描述：如上圖，這裡原先的Voronoi圖是已經按照DCEL的數據結構存儲好，並且圖中的編號順序只是為了描述方便不代表輸入時是有這個次序。假設引入一個新的site點4，那麼首先和0號site一起找到它們的平分線，並且通過0Cell的邊界點找到這條平分線的端點，然後在通過DCEL結構中存儲的內容翻到隔壁1號Cell中繼續找1號site與4號site的平分線，再找到它的端點。就這樣依次尋找直到封閉。

如圖所示，在引入黃色的點後產生新的平分線的順序是1234，那麼Voronoi邊的遍歷順序則是acdefghijb。

演算法複雜度：從求交開始每次沿著一個平分線的方向去做一次求交，由於Cell本身已經存為DCEL結構，根據Voronoi圖的性質每一個Cell都是凸的。在一個凸多邊形中去對邊界做一個這樣的穿刺的求交是在O(logn)的時間內完成的。用O(1)的時間翻牆，再用O(1)的時間確定平分線的方向繼續前行。而每一個新引入的點邊界的規模不超過n，整個演算法是引入n個點，因此最後演算法的複雜度是O(n2logn)。

11、Divided-And-Conquer

分而治之：首先將整個坐標的點集沿著x軸坐標做一個預排序，然後將點集大概平均地分割成更小的兩個點集進行遞歸構造Voronoi圖，最後Merge。

偽代碼：

DacVoronoi(S, n){ x-sort all sites into S = {p1, p2, ..., pn}; return dacVD(S, 1, n);}dacVD(S, i, j){ return (j - i < 3) ? trivialVD(S, i, j) : merge(dacVD(S, i, (i + j)/2), dacVD(S, (i + j)/2 + 1, j);}

處理重疊部分

在Merge兩個Voronoi子圖的時候經常會產生重疊，對於重疊我們要根據它們之間的平分線的平面來對它們進行分割。平分線對應的左平面切除右邊的Cell，反之右平面切除左邊的Cell。

如果單純用這種方法強行處理一系列的重疊的話，複雜度會比較高，下面介紹一種優化的方法。

輪廓線（Contour）：介於左邊的子圖和右邊子圖之間的邊界，它到左側site和右側site的距離是相等的，它具有等距性。因此Contour上的任何一個點相對於最後要合成的Voronoi圖來說必然是某一條edge上的點，所以Contour必然是由最終的Voronoi圖上的若干條edge前後依次相連而構成的一條裂縫。

Contour的性質：

①具有y方向上的單調性，是y方向上單調的一條折線，即任何一個水平高度上這樣的contour line只會至多有一個交點。

②一條contour在自向而下的行進過程中，它的第一段即上面通向無窮的那一段必然是左右兩個子集的公切線的平分線。對稱的最後一段即通往負無窮深度的奶段也必然是lower common tangent的平分線。

③若左右各有n和m個site，那麼contour的長度不會超過n+m

下面進行Merge的講解

演算法描述：首先找到Contour入手的第一條邊，即先找左右子圖的公切線（與凸包演算法中的類似只需線性時間），然後求它的平分線記做b；接著自頂而下的沿著contour鏈追蹤下去，對於任意一對左右site，我們都找出它們之間的平分線，這裡是一個迭代的過程；對於每一次找到的平分線b，要對左邊的Cell和右邊的Cell同時用b做一次裁切（求交找方向）；裁切後要更新下一個Cell，這裡的的關鍵是看這個平分線是最先從哪個cell出來的，如果一個先出來那麼另一個就要保持。而先出來的Cell要替換為它同側的一個後繼。我們要用它的後繼來構成下一對需要排解衝突的Cell pair。對於新的Cell，它們的平分線又要重新確定。這個過程一直持續到從contour的最後一條邊出來。（這裡的描述比較亂...）

偽代碼描述：

ComputeContourBetween(VD(SL),VD(SR)){ compute the upper tagent of conv(SL) and conv(SR); //let l∈SL and r∈SR be tagent sites and b be the bisector of segment lr trace the contour from top down; find b ∩ Cell(l) and b ∩ Cell(r); clip and then flip the cell whose boundary intersects b first; update l or r; update b;}

對於Merge的演算法複雜度主要體現在求交上，因為有可能會在某一個Cell上反覆的與其他平分線求交，這裡的反覆計算就對複雜度造成了很大影響。

由於Contour具有凸性，那麼我們可以利用這一性質來對Merge演算法進行優化。

如圖所示，我們可以發現Contour每次拐彎都是同一個方向的，這意味著contour上這樣一系列的邊參與構成了這個site經過剪裁以後更小的那個cell的邊界，它們會構成一條凸的環路。那麼具體來說如果是在左側的某一個cell中，則所有的拐向都是朝右，反之亦然。

而我們在求交過程中，雖然能確定拐的方向，但是如上圖所示我們還會得到類似點1那樣的無用點，其實我們只需要用更近的那個交點。正是有這些貌似無用點的求交導致複雜度的增加，因為每次都要從起點遍歷。由於contour的凸性，我們可以得到這些貌似無用的交點在整個這個cell的邊界上的分布是前後單調的。

因此我們的演算法優化就在於，假設黃色點1是我們找到的第一個交點，那麼接下來的遍歷只需要從點1開始即可而不需要再從頭開始遍歷。

改進後，所有這些交點的求法都可以在前一個交點的基礎上繼續搜索，它的成本就是連續的兩個交點之間的一段弧的長度，總體不會超過這個Cell的軸長，是一個線性的操作。

那麼基於這樣的一個合併的基本演算法，按照分而治之的框架所得到的總體的Voronoi圖的構造演算法複雜度不超過O(nlogn)。

12、Plane-Sweep

假設用水平線自頂而下掃描平面，再引入了一些拋物線線段如下圖。

我們在曲線上面的部分叫做封存部分（Frozen region），曲線和掃描線之間的叫做未凍結部分（Unfrozen region）。Frozen部分的特性從數學上來說是它到掃描線的距離都要大於它到以上已掃描過的點集的距離；反過來，Unfrozen部分都是到這個掃描線的距離更短，至少相對於已經掃過的那些site而言更短。

我們將那條曲線取名叫做Beach Line（海浪線）。數學上的定義是這條線上的點到掃描線的距離等於它掃過的site的最下的距離。而在Frozen內部的點都已經是確定的落在某個Cell，因為它到掃描線的距離都要大於它到已掃過的點集中離它最近的那個site的距離，因此Frozen region是已經確定了的部分。

準備工作：

拋物線的定義：到準線和焦點距離相等的點的集合。性質：準線離焦點越近，拋物線開口越狹窄。當準線與焦點重合時，此時的拋物線是一條直線。

對於我們這裡而言，準線就是那條掃描線，每個掃過的site都可以是焦點，可以說掃過多少個site就有多少條拋物線。beach line就是最底下的輪廓，稱作包絡（envelope）。這些拋物線有的並不貢獻Beach line有的貢獻好幾段，一條拋物線最多貢獻n條弧。而在任意時刻beach line上的弧的數目不超過2n-1段。

在beach line中兩段弧的交點稱作breakpoint，這個交點一定會位於某條Voronoi edge上。隨著掃描線的推進，breakpoint會不斷前進構成Voronoi edge，直到掃描線碰到另一個site，此時的breakpoint就是Voronoi vertex。

當然實際演算法過程中不可能處理無數個點，我們需要針對一些特定的位置進行處理，這些我們也稱作Events事件。這個Events指的是整個掃描線上的拋物線的拓撲結構發生變化的時刻。這些變化的時刻分為了兩類。

（1）、Circle Events

circle event是動態生成的，隨著演算法的進行不斷的發現circle event。

若在beach line上出現了新的三個相鄰的夥伴弧，分別對應於i,j,k三個site，它們所對應的三段拋物線弧首尾相連，構成這樣的局部三人組必會定義一個圓，那麼這個圓最下面的點就是一個circle event。

由Voronoi圖定義可知，若出現這麼一個圓，那麼掃描線上這個圓一定是空的。若抵達最低點時圓仍是空的，那麼此時i的拋物線和k的拋物線的交匯點就是一個新的Voronoi vertex。在這個縫合處會長出一條新的邊，這條邊的方向就是i和k的平分線的方向。這個過程會不斷的演化下去。

在碰到circle event後①將j對應的弧從beach line中刪除②生成一個新的vertex③將原來的兩條綠色的平分線的終點綁定在新的vertex上④生成一條新的邊，方向為i k的平分線方向⑤刪除包含j的circle event⑥檢測i k的兩邊是否會有新的三元組產生。

（2）Site Events

掃描點經過適當掃描後碰到一個site，①確定這個site上方對應的弧是哪段弧②將對應的弧p用一段無限小的弧split成兩段③隨著掃描線往下，焦點s與掃描線生成的拋物線在弧p中間對應的那一小段弧會不斷擴大，此時對應的兩個breakpoint連接的線稱作懸垂線④將原先p和q的三人組對應的circle events刪除⑤對於每個新產生的三元組，創造新的circle events。

當最後抵達新產生的circle event c時，之前的懸垂線和以前p和q的平分線就會匯聚到點v中併產生黃色的新的平分線。