Voronoi Diagram

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

簡單來說，鄰近的點的中垂線，形成Voronoi Diagram。

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

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

UVa 12109

Perpendicular Bisector

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

Line pb(Point a, Point b) { // ab中點。 Point c = (a + b) / 2.0; // ab向量，顛倒、變號，得到法向量。 Point s = b - a; swap(s.x, s.y); s.x *= -1; // 中垂線。兩點得一線。 return (Line){c, c + s}; }

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

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

Voronoi Diagram點和邊的數量

延伸至無限遠的邊，通通接往一個點，Voronoi Diagram就變成平面圖。

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

演算法（Half-plane Intersection）

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

演算法（Incremental Method）

online演算法，一次加一點。找到當前輸入點相距最近的點，然後以中垂線繞行一圈求得當前輸入點的區域。時間複雜度O(N²)。

演算法（Divide-and-Conquer Method）

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

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

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

演算法（Fortune's Algorithm）

平移的掃描線。時間複雜度O(NlogN)。

實務上最快的演算法。

Delaunay Triangulation

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則有許多種。

性質：Empty Circumcircle Property

三角形外接圓，內部不含任何點。證明省略。

性質：Maxmin Angle Triangulation

最小角盡量大。證明省略。

Voronoi Diagram是中垂線與距離，Delaunay Triangulation是圓與角度。

演算法（Lawson's Flip Algorithm）

隨意求出一個三角剖分。不斷翻轉不符空圓性質的邊，使最小角逐漸增大（或者最小角不變、次小角增大，以此類推）。每一條邊頂多翻轉一次。時間複雜度O(N²)。

演算法（Bowyer–Watson Algorithm）

online演算法，一次加一點。不符空圓性質的三角形，形成一個多邊形，清除內部所有邊，重新連接當前點與多邊形頂點，就得到Delaunay Triangulation。時間複雜度O(N²)。

演算法（Divide-and-Conquer Method）

所有點分成左右兩側，分別求出Delaunay Triangulation，然後合而為一。

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

演算法（Sweep Circle Algorithm）

旋轉的掃描線。時間複雜度O(NlogN)。

實務上最快的演算法。

延伸閱讀：勢力消長

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

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

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

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

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

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

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

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

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

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

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

延伸閱讀：點改成球

Power Diagram與Regular Triangulation。

延伸閱讀：拋物面

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

割面與拋物面的交集，投影至XY平面，恰是圓。

點座標(x, y)改成(x, y, x²+y²)，求得三維凸包。

下凸包，投影至XY平面（自下方無限遠處仰視），恰是Nearest Point Voronoi Diagram的對偶圖，也就是Delaunay Triangulation。

上凸包，投影至XY平面（自上方無限遠處俯視），恰是Farthest Point Voronoi Diagram的對偶圖。

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

兩切點、兩切面的交集，投影至XY平面，恰是中垂線。

點座標(x, y)改成(x, y, x²+y²)，求得切面們的三維包絡面。

下包絡面，投影至XY平面，恰是Delaunay Triangulation。

上包絡面，投影至XY平面，恰是Voronoi Diagram。

Nearest Neighbor Graph

  Nearest Neighbor Graph            各點連往最近鄰居
⊆ Euclidean Minimum Spanning Tree   最近點對相連，形成環則捨棄
⊆ Relative Neighborhood Graph       兩點相連，當其他點距離都更遠
⊆ Gabriel Graph                     兩點相連，當外接圓不含其他點
⊆ Delaunay Graph (1-Skeleton)       三點相連，當外接圓不含其他點

α-Shape    https://en.wikipedia.org/wiki/Alpha_shape
β-Skeleton https://en.wikipedia.org/wiki/Beta_skeleton
Θ-Graph    https://en.wikipedia.org/wiki/Theta_graph
Yao Graph  https://en.wikipedia.org/wiki/Yao_graph

ICPC 3270

Euclidean Graph

邊的權重，等於二維平面的直線距離。

儘管Euclidean Graph是二維平面上的圖，但是它跟Planar Graph沒有任何關係。

L₂-Norm Nearest Neighbor Search

已知一群點（固定），給定一個點（變動），從中找到最近點。

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

Locality-sensitive Hashing。O(N)。

L₂-Norm All Nearest Neighbors

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

L₂-Norm Farthest Neighbor Search

已知一群點（固定），給定一個點（變動），從中找到最遠點。

我沒有研究。

L₂-Norm All Farthest Neighbors

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

窮舉法。O(N²)。

Farthest Voronoi Diagram。O(NlogN)。

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

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)。

struct Point {int x, y, z;} p[10]; int f(int a, int b, int c) { int max = -1e9, min = 1e9; for (int i=0; i<10; i++) { int v = a * p[i].x + b * p[i].y + c * p[i].z; max = std::max(max, v); min = std::min(min, v); } return max - min; } float farthest_pair() { return max(max(f(1,1,1), f(1,1,-1)), max(f(1,-1,1), f(-1,1,1))); }

UVa 11012

L₁-Norm Mininum Spanning Tree

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

ICPC 3662