Voronoi Diagram

Voronoi Diagram

平面上散布許多點。平面上每一處,各自歸類於最近的點;自然而然的,形成了分界線,是中垂線。Voronoi Diagram是分界線組成的集合。Voronoi是發明者的姓氏。

換個角度看。鄰近的點的中垂線,形成Voronoi Diagram。

Voronoi Diagram隱含著鄰近的資訊,所以「最靠近」、「距離最短」之類的問題,多半可以透過Voronoi Diagram解決。

Voronoi Diagram是大自然的圖案,諸如長頸鹿的斑紋、蜻蜓的翅膀、葉片的細胞壁。應用相當廣泛。

UVa 12109

Perpendicular Bisector

「中垂線」,中學數學,不再贅述。

三角形的三中垂線,交於一點,是外接圓圓心,稱作外心。中垂線有等距、平分的感覺,圓有等距、歸心的感覺,兩者關係匪淺。

由此可知,Voronoi Diagram一個點至少連著三條邊。

Voronoi Diagram點和邊的數量

Voronoi Diagram看上去就像個平面圖。延伸至無限遠的邊,通通接往一個點,Voronoi Diagram就變成平面圖。

運用平面圖歐拉公式v-e+f=2,輔以「一個點至少連著三條邊」的限制,可以推理出Voronoi Diagram最多有2N-5個點、3N-6條邊,都是O(N)。

延伸閱讀:勢力消長

每個點設定不同的強度,兩點之間依照強度比例劃定界線。理論上可以生成所有平面圖?

延伸閱讀:歸類於第k近的點

平面上每一處,各自歸類於第k近的點,就形成了Order k Voronoi Diagram。至於這有什麼用途,我也不知道。

為了辨識每塊區域歸類於哪一點,我們將每個點標上不同顏色,讓區域的顏色對應點的顏色。

上方圖片以HTML5 Canvas繪製而成,演算法是窮舉法。有興趣的讀者請自行檢視網頁原始碼。

延伸閱讀:歸類於最遠的點

既有最近,亦有最遠。平面上每一處,各自歸類於最遠的點,就形成了Farthest Point Voronoi Diagram。

換個角度看。相離最遠的點,自然而然都在凸包上,證明請參考「Farthest Pair」。相離最遠的點的中垂線,形成Farthest Point Voronoi Diagram。

延伸閱讀:點改成其他東西

我們可以把一個點改成一個圓、一條線段、一群點、一個多邊形等等圖形,得到各式各樣的Voronoi Diagram。

這些都是進階課題,有興趣的讀者請自行尋找資料。

演算法(Half-plane Intersection)

枚舉每一點,求得該點的區域:與其他點形成的N-1條中垂線,求半平面交集。時間複雜度為O(N ⋅ NlogN)。

演算法(Incremental Method)

http://nodename.com/wpEmbeds/VoronoiToy/bin/PlanePointsApp.swf

online演算法,一次加一點。先找到當前輸入點相距最近的點,然後以中垂線繞行一圈求得當前輸入點的區域。

Voronoi Diagram的點數和邊數都是O(N)。就算是窮舉路線轉折點所在的邊,整體時間複雜度仍是O(N²)。

演算法(Divide and Conquer)

http://students.info.uaic.ro/~emilian.necula/vor2.pdf

所有點分成左右兩側,分別求出Voronoi Diagram,然後合而為一。

從左右Convex Hull的外公切線的中垂線開始行進,一旦撞到左右Voronoi Diagram,就改變行進方向。

至於要如何清除多餘的Voronoi Diagram,我也不知道。

時間複雜度是O(NlogN),然而步驟繁雜,運行極慢,不實用。讀者只需知道Voronoi Diagram存在這麼一個解題策略就行了,不需浪費時間鑽研細節。

演算法(Fortune's Algorithm)

http://www.cs.hmc.edu/~mbrubeck/voronoi.html

平移的掃描線。時間複雜度是O(NlogN),實務上效率極佳。

Delaunay Triangulation

Voronoi Diagram與Delaunay Triangulation

Delaunay是Voronoi的博士班學生。Delaunay Triangulation起初是從Voronoi Diagram發展來的。

Voronoi Diagram變Delaunay Triangulation:以直線連結相鄰的點。簡單來說就是平面對偶、邊拉直。時間複雜度O(N)。

Delaunay Triangulation變Voronoi Diagram:以直線連結相鄰的三角形的外接圓圓心,並且補上凸包每一條邊的中垂線。時間複雜度O(N)。

Delaunay Triangulation的數量

只有三點以下共圓,Voronoi Diagram與Delaunay Triangulation只有唯一一種,互相對應。

出現四點以上共圓,Voronoi Diagram仍然只有唯一一種,Delaunay Triangulation則有許多種。

性質:三角形外接圓,內部不含任何點

【待補證明】

性質:最小的角盡量大

【待補證明】

Voronoi Diagram與Delaunay Triangulation,聚集了鄰近的點,排斥了偏遠的點。

Voronoi Diagram的外表是中垂線與距離,Delaunay Triangulation的內裡則是圓與角度。

演算法(Edge Flip Algorithm)

隨意求出一個三角剖分。不斷翻轉不符空圓性質的邊,使最小角逐漸增大(或者最小角不變、次小角增大,以此類推),就得到Minmax Angle Triangulation。時間複雜度不明。

【待補證明】

演算法(Incremental Method)

online演算法,隨時維護一個Minmax Angle Triangulation。

每當輸入一點,馬上尋找不符空圓性質的三角形們,形成一個多邊形,清除內部的邊,連接當前輸入點與多邊形頂點們,就得到Minmax Angle Triangulation。時間複雜度O(N²)。

採用Flip Edge Algorithm,配合特殊資料結構,可以加速至O(NlogN)。此處略過不提。

演算法(Divide and Conquer)

O(NlogN)。

Power Diagram(Under Construction!)

Power Diagram

點改成圓。

Regular Triangulation(Under Construction!)

Power Diagram與Regular Triangulation

power diagram = 球法線距離平方
regular triangulation = 球切線距離平方
https://www.kiv.zcu.cz/site/documents/verejne/vyzkum/publikace/technicke-zpravy/2009/tr-2009-03.pdf 
兩點正規性 = 兩球交點到兩球球心是直角
正心regular center = 正心設定適當權重,與四面體的四個點皆正規
(若在平面上,圓心太近夾角小,圓心太遠夾角大,所以至少要三維空間)
空球性質 = 四面體正心,空間其餘點通通離正心太遠、通通在球外。
      (正心與其權重可以視作球)
regular triangularization = 所有四面體都滿足空球性質。
channel = 三維空間一堆球之間有多大空隙可以走動,蛋白質docking

Point-Line Duality(Under Construction!)

Convex Hull與Envelope互為點線對偶

點集合求凸包,點線對偶,直線集合以半平面交集求包絡線。

也就是說,求半平面交集的困難度等同於求凸包的困難度。

【待補文字】

UVa 11756

增加一個維度的Convex Hull

點座標(x, y)改成(x, y, x²+y²)之後,呈現拋物面。

平面與拋物面的交集,投影至XY平面,恰是圓。圓半徑為r,平面與切面距離為r²。

【待補圖片】

求得新座標的3D Convex Hull:

自下方無限遠處仰視(下凸包投影至XY平面),就是Nearest Point Voronoi Diagram的對偶圖,空圓的三角剖分,也就是Delaunay Triangulation。

自上方無限遠處俯視(上凸包投影至XY平面),就是Farthest Point Voronoi Diagram的對偶圖。

【待補圖片】

增加一個維度的Envelope

點座標(x, y)改成(x, y, x²+y²)之後,呈現拋物面。

兩個座標,其兩個切面交集,投影至XY平面,恰是中垂線。

【待補圖片】

求得新座標的切面的3D Envelope:

自下方無限遠處仰視(下包絡面投影至XY平面),就是Delaunay Triangulation。

自上方無限遠處俯視(上包絡面投影至XY平面),就是Voronoi Diagram。

【待補圖片】

Neighbor

Nearest Neighbor Graph

https://en.wikipedia.org/wiki/Nearest_neighbor_graph

ICPC 3270

Relative Nearest Neighbor Graph

http://en.wikipedia.org/wiki/Relative_neighborhood_graph

Gabriel Graph

http://en.wikipedia.org/wiki/Gabriel_graph

α-Shape

http://en.wikipedia.org/wiki/Alpha_shape

β-Skeleton

http://en.wikipedia.org/wiki/Beta_skeleton

Θ-Graph

http://en.wikipedia.org/wiki/Theta_graph

Yao Graph

http://en.wikipedia.org/wiki/Yao_graph

Neighbor

L₂-Norm Nearest Neighbor Search

已知一群點(固定),給定一個點(變動),從中找到最近點。

同義詞:L₂-Norm = Euclidean。Nearest = Closest。Search = Query。

Locality-sensitive Hashing。O(N)。

http://blog.csdn.net/icvpr/article/details/12342159

L₂-Norm All Nearest Neighbors

已知一群點,求每個點的最近點。顯然涵蓋了「最近點對」。

https://algnotes.wordpress.com/2015/03/12/

L₂-Norm Farthest Neighbor Search

已知一群點(固定),給定一個點(變動),從中找到最遠點。

我沒有研究。

L₂-Norm All Farthest Neighbors

已知一群點,求每個點的最遠點。顯然涵蓋了「最遠點對」。

窮舉法。O(N²)。

Farthest Voronoi Diagram。O(NlogN)。

動態問題,更新、查詢的平均時間複雜度是O((logN)²)。

http://www.ics.uci.edu/~eppstein/pubs/Epp-CGTA-96.pdf

L₂-Norm All Farthest Neighbors on Convex Hull

無法使用旋轉卡尺。例如一個橢圓。

Randomized Incremental Method。O(NlogN)。

Monge Matrix + SMAWK Algorithm。O(N)。

UVa 12311

L₂-Norm Mininum Spanning Tree

Kruskal's Algorithm。O(ElogV) = O(N²logN)。

Prim's Algorithm。O(N²)。

Voronoi Diagram。O(NlogN)。

L₁-Norm All Nearest Pairs

ICPC 5848

L₁-Norm Farthest Pair

距離公式|x1 - x2| + |y1 - y2| + |z1 - z2|。去掉絕對值,共8種情況。以(x1 - x2) - (y1 - y2) + (z1 - z2)為例,重新整理得到(x1 - y1 + z1) - (x2 - y2 + z2)。若前項盡量大、後項盡量小,則距離越大。

窮舉8種正負號配置情況(因為對稱,其實只需4種)。對於一種情況,窮舉每個點,記錄最大值、最小值。最大值減最小值,即為所求。時間複雜度O(N)。

UVa 11012 Sphere DISTANCE

L₁-Norm Mininum Spanning Tree

http://blog.csdn.net/acm_cxlove/article/details/8890003

邊數降至4N,可套用Kruskal's Algorithm。O(NlogN)。

ICPC 3662