5.4 算法
(Algorithms)

维诺多边形(Voronoi diagram)的广泛应用及其内在的美感激发了研究人员发明各种算法来计算它。在本节中，我们将简要地考察四种算法，因为我们将在 5.7.2 节中看到，维诺多边形可以使用我们的凸包（convex hull）代码来计算。

5.4.1. 半平面求交(Intersection of Halfplanes)

我们可以根据公式 (5.2)，通过求 \(n-1\) 个半平面的交集来分别构建每个维诺多边形区域。构建 \(n\) 个半平面的交集与在二维空间中构建 \(n\) 个点的凸包是对偶任务，并且可以在 \(O(n \log n)\) 时间内用类似的算法完成(练习 6.5.3[5])。对每个站点都这样做，代价将是 \(O(n^2 \log n)\)。

5.4.2. 增量构造(Incremental Construction)

假设已经构建了 \(k\) 个点的维诺多边形 \(\mathcal{V}\)，现在我们要添加一个点 \(p\) 后构建新的图 \(\mathcal{V}'\)。假设 \(p\) 在与几个维诺多边形顶点相关联的圆内，记为 \(C(v_1), \dots, C(v_m)\)。那么 \(\mathcal{V}\) 的这些顶点不可能是 \(\mathcal{V}'\) 的顶点，因为它们违反了维诺多边形顶点圆内必须不包含任何站点这一条件(V5，5.3.2 节)。事实证明，\(\mathcal{V}\) 中的这些顶点是不会被带入 \(\mathcal{V}'\) 的。并且，这些顶点都集中在图的一个区域内。这些模糊的观察结果可以精确的表述出来，它们构成了构建维诺多边形最简洁的算法之一(Green & Sibson 1977)。该算法在每次点插入时花费 \(O(n)\) 时间，总复杂度为 \(O(n^2)\)。尽管它是二次复杂度，但一直是构建该图最流行的方法。有关实现细节，请参阅 Field(1986)。

增量算法最近通过随机化重新焕发了活力，我们将在 5.7.4 节中简要提及。

5.4.3. 分治算法(Divide and Conquer)

维诺图(Voronoi diagram)可以通过一种复杂的分治算法在 \(O(n \log n)\) 时间内构建出来。该算法由 Shamos & Hoey(1975) 首次详细阐述。正是这篇论文将维诺图引入了计算机科学界。这种时间复杂度是渐近最优的，但该算法相当难以实现。不过，只要仔细设计数据结构，这也是可以做到的。参见 (Guibas & Stolfi 1985)。

我们将略过这个具有历史意义的算法，转而关注一些近期令人振奋的进展。

5.4.4. Fortune 算法

直到 1980 年代中期，大多数计算维诺图的实现，为了避免分治法编码的复杂性而接受了其较慢的性能，使用的是 \(O(n^2)\) 的增量算法。但在 1985 年，Fortune (1987) 发明了一种巧妙的平面扫描算法，它像增量算法一样简单，最坏情况复杂度是 \(O(n \log n)\) 的。我们现在将概述该算法背后的主要思想。

平面扫描算法(2.2.4 节)用一条线在平面上扫过。扫过的平面部分，问题都已解决。而对于尚未到达的部分，仍需努力。用于构建维诺图的平面扫描算法会在扫描线后构建该图。初看起来，这似乎是不可能的，因为维诺区域 \(V(p)\) 的维诺边有可能会在扫描线 \(L\) 遇到负责该区域的站点 \(p\) 之前就被扫描线 \(L\) 遇到。 Fortune 通过一个极其巧妙的想法克服了这一看似不可能的问题。

圆锥

三维坐标系的 \(x-y\) 平面上有一些站点。在每个站点 \(p\) 上方建立一个圆锥，顶点在 \(p\)，且侧面倾斜角为 45°。如果将第三维视为时间，那么 \(p\) 上方的圆锥代表一个以单位速度围绕 \(p\) 扩大的圆，经过 \(t\) 个单位时间后，其半径为 \(t\)。

现在考虑两个相邻的圆锥，分别位于站点 \(p_1\) 和 \(p_2\) 上方。它们在空间中相交于一条曲线。从维诺图的扩大圆视图来看，这条曲线完全位于一个垂直平面内，即垂直于 \(p_1 p_2\) 平分线的平面。见图 5.9。因此，尽管交线在三维中是弯曲的，但它投影到 \(xy\) 平面上是一条直线。

如果所有站点上方的圆锥都是不透明的，并且从 \(z = -\infty\) 处观察，看到的正是维诺图！

圆锥切片

现在我们可以来讨论 Fortune 的思想了。他的算法用一个倾斜平面 \(\pi\) 扫描这些圆锥，该平面与 \(xy\) 平面成 45° 斜角。扫描线 \(L\) 是 \(\pi\) 与 \(xy\) 平面的交线。假设 \(L\) 平行于 \(y\) 轴，且其 \(x\) 坐标为 \(\ell\)。如图 5.10 所示。 \(\pi\) 以及所有圆锥都是不透明的，我们来考虑 \(z = -\infty\) 处的视图。

在 \(L\) 的 \(x > \ell\) 一侧，从下方只能看到 \(\pi\)。它在 \(xy\) 平面下方切割，因此遮挡了站点和圆锥。这代表尚未被扫描的平面部分。在 \(L\) 的 \(x < \ell\) 一侧，在 \(\pi\) 与右侧(正 \(x\))圆锥"前沿frontier"的交线之前可以见到维诺图。 \(\pi\) 与任何一个圆锥的交线都是一条抛物线(圆锥曲线的基本性质)，因此从 \(z = -\infty\) 看起来 \(\pi\) 与这个右侧前沿的交线投影到 \(xy\) 平面上是一条"抛物线前沿parabolic front"，一条由抛物线段组成的曲线。如图 5.11 所示。两条抛物线在 \(\pi\) 与两个圆锥相遇的地方连接。根据我们上面关于两个圆锥相交的讨论，这一定是在一条维诺边上。

抛物线前沿

现在我们终于可以看到 Fortune 是如何解决扫描线在生成站点之前遇到维诺边的问题的了。因为他的扫描平面 \(\pi\) 的倾斜角度与圆锥侧面相同， \(L\) 遇到站点 \(p\) 的时刻正是 \(\pi\) 首次击中 \(p\) 上方圆锥的时刻！因此，并非维诺图在任何时候都构建在 \(L\) 的左侧，而是它始终构建在 \(\pi\) 下方，这意味着它是构建在 \(L\) 左侧直到抛物线前沿的部分，而前沿稍微滞后于 \(L\)。

算法始终在维护抛物线前沿，其抛物线前沿的融合轨迹，可以描绘出维诺图，因为这些折点都位于维诺边上。虽然我们对算法的描述远未完成，但我们不再尝试在此详述。

算法只需要存储抛物线前沿，其大小为 \(O(n)\) 且通常为 \(O(\sqrt{n})\)。这是 Fortune 算法在 \(n\) 很大时的一个显著优势。任何时候所需的存储空间通常远小于图的大小。一些场景，比如基于地理信息系统收集的数据绘制的图，\(n\) 就很大，可能有 \(10^6\) (Sugihara & Iri 1992)。

5.4.5. 练习

\(\mathcal{D}(P) \Rightarrow \mathcal{V}(P)\)。设计一个算法，在给定 Delaunay 三角分割的情况下计算维诺图。尝试达到 \(O(n)\) 的时间复杂度。
一维维诺图 One-dimensional Voronoi diagrams。直线上一组点 \(P = \{p_1, \dots, p_n\}\) 的一维维诺图是一组点 \(\mathcal{V}(P) = \{x_1, \dots, x_{n-1}\}\)，使得 \(x_i\) 是 \(p_i p_{i+1}\) 的中点。假设给你一个集合 \(X = \{x_1, \dots, x_{n-1}\}\)。设计判据来断定 \(X\) 是否是一组点的一维维诺图，如果是，确定 \(P\)。该算法的可以有多快？
动态维诺图 Dynamic Voronoi diagrams。想象一组在平面上移动的点，每个点都有固定的速度和方向。设 \(V(t)\) 为时间 \(t\) 时这些点的维诺图。获得所有时间内可能产生的组合不同图的数量紧致界(tight bounds)是一个未解决的问题。在这里，我要求你建立最著名的下界，\(\Omega(n^2)\)。换句话说，找到一组 \(n\) 个移动点，使得 \(V(t)\) 的组合结构变化 \(cn^2\) 次，\(c\) 是某个常数。目前还没有人找到变化次数超过 \(n^2\) 的例子，但最好的上界大约是 \(O(n^3)\) (Fu & Lee 1991), Guibas, Mitchell & Roos (1991)。
任意三角剖分 Arbitrary triangulation。设计一个算法来找到点集 \(P\) 的任意三角分割，即一组与 \(P\) 中每个点相关联的对角线，将 \(\mathcal{H}(P)\) 划分为三角形。由于不要求三角分割必须是 Delaunay 的，这个自由度就很大了。
翻转算法 Flipping algorithm。研究以下构建 \(\mathcal{D}(P)\) 的算法，从 \(P\) 的任意三角分割开始。然后重复以下过程直到达到 \(\mathcal{D}(P)\)。识别两个共享对角线 \(bc\) 的相邻三角形 \(abc\) 和 \(cbd\)，使得四边形 \(abcd\) 是凸的。如果 \(d\) 在 \(abc\) 的外接圆内，则删除 \(cb\) 并添加 \(ad\)。这样可行吗？

5.4 算法(Algorithms)