Question

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。

这些都是进阶课题，有兴趣的读者请自行寻找资料。

Voronoi Diagram: Half-plane Intersection

枚举每一点，求得该点的区域：与其他点形成的 N-1 条中垂线，求半平面交集。时间複杂度为 O(N * NlogN)。

Voronoi Diagram: Incremental Method

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

online 演算法，一次加一点。先找到当前输入点相距最近的点，然后以中垂线绕行一圈求得当前输入点的区域。

Voronoi Diagram 的点数和边数都是 O(N)。就算是穷举路线转折点所在的边，整体时间複杂度仍是 O(N^2)。

附带一提，当给定的点都在凸包上时，使用 Randomized Incremental Method 可达 O(N)。

http://www.cs.dartmouth.edu/reports/TR90-147.pdf

Voronoi Diagram: Divide and Conquer

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

所有点分成左右两侧，分别求出 Voronoi Diagram，然后合而为一。

从左右 Convex Hull 的外公切线的中垂线开始行进，一旦撞到左右 Voronoi Diagram，就改变行进方向。

至于要如何清除多馀的 Voronoi Diagram，我也不知道。

时间複杂度是 O(NlogN)，然而步骤繁杂，运行极慢，不实用。读者只需知道 Voronoi Diagram 存在这麽一个解题策略就行了，不需浪费时间鑽研细节。

Voronoi Diagram: Fortune's Algorithm

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

平移的扫描线。时间複杂度是 O(NlogN)，实务上效率极佳。