2.4 线性时间三角化
(Linear-Time Triangulation)
至少 1911 年(Lennes 1911) 证明中就已经隐含了 \(O(n^2)\) 复杂度的三角化算法。2.1 节中描述的 \(O(n \log n)\) 算法是计算几何早期的成就之一，发表于 1978 年，就在 Shamos 在其论文中命名该领域三年之后。 很快，\(O(n \log n)\) 是否是三角化的最优解这一问题就成为计算几何中尚未解决的关键问题，并由此催生了各种各样巧妙的算法。 人们发现了一些能够突破 \(n \log n\) 限制的算法，但仅限于一些特殊情况，参见表 2.1 中的示例。最坏情况仍然是 \(O(n \log n)\)。
Table 2.1. 三角化算法史
| Year | Complexity | Reference |
|---|---|---|
| 1911 | \(O(n^2)\) | Lennes(1911) |
| 1978 | \(O(n \log n)\) | Garey et al.(1978) |
| 1983 | \(O(n \log r)\), \(r\) reflex | Hertel & Mehlhorn(1983) |
| 1984 | \(O(n \log s)\), \(s\) sinuosity | Chazelle & Incerpi(1984) |
| 1988 | \(O(n + n t_0)\), \(t_0\) int. triangs | Toussaint(1990) |
| 1986 | \(O(n \log \log n)\) | Tarjan & Van Wyk(1988) |
| 1989 | \(O(n \log^* n)\) randomized | Clarkson, Tarjan & Van Wyk(1989) |
| 1990 | \(O(n \log^* n)\) bnded. ints | Kirkpatrick, Klawe & Tarjan(1990) |
| 1990 | \(O(n)\) | Chazelle(1991) |
| 1991 | \(O(n \log^* n)\) randomized | Seidel(1991) |
经过十年的努力，Tarjan & Van Wyk(1988) 发现了 \(O(n \log \log n)\) 的算法。这一突破引发了一系列研究，其中包括两个 \(O(n log^* n)\) 算法， 一个是随机算法，另一个是针对具有有界的整数坐标的多边形的算法。
Chazelle 于 1991 年构造出了一个卓越的算法最坏情况复杂度为 \(O(n)\)，结束了学术界长达十三年的研究。详细描述该算法会远远超出我们的讨论范围，但我会提供一个大致的概述。
该算法主要是在计算一个可见性图visibility map，它是对梯形化的推广，在多边形链的每个顶点两侧绘制水平弦。 当链是多边形时，这相当于将弦向多边形的外部和内部延伸。Chazelle 解释道，他的算法模拟了归并排序，这是一种常用的分治排序技术。 具有 \(n\) 个顶点的多边形被分割成具有 \(n/2\) 个顶点的链，这些链又被分割成具有 \(n/4\) 个顶点的链，依此类推。 通过合并子链的可见性图，获得链的可见性图。这使得该算法的时间复杂度为 \(O(n \log n)\)。
Chazelle 对此进行了改进，将整个过程分为两个阶段。在第一阶段，仅粗略地计算可见性图的近似值，粗略到足以在线性时间内完成合并。 这些图之所以粗略，是因为它们缺少一些弦。第二阶段则在线性时间内细化得到完整的可见性图。然后和之前介绍的算法一样，根据可见性图定义的梯形化生成三角分割。 细节非常复杂。
虽然该算法解决了一个长期存在的开放难题，但找到一种简单、快速、实用的多边形三角化算法仍然是一个开放性问题。 很快出现了几个候选算法，包括 Seidel 的随机 \(O(n \log^* n)\) 算法，我们将在此简要介绍该算法(Seidel 1991)。
2.4.1. 随机三角化(Randomized Triangulation)
Seidel 的算法遵循2.3节的计算路径，梯形化 \(\Rightarrow\) 单调山峰 \(\Rightarrow\) 三角剖分径。 他的改进之处在于能够快速梯形化。他将一组线段的可见性图构建成一个“查询结构query structure” \(Q\)， 该数据结构可以在与深度成正比的时间内，定位其所在梯形中的点。我们将在第7章(7.11节)中详细描述该结构。 现在，大致了解就足够了。
对于 \(n\) 个线段，构造的数据结构深度可以是 \(\Omega(n)\)。如果是通过随机添加线段逐步构建的，那么在 \(Q\) 中定位一个点的预期成本为 \(O(\log n)\)。 这就是“随机randomized”的含义。它使用抛硬币的方式来决定接下来添加哪个线段。算法并不假设线段本身在任何意义上的随机分布。 这样的假设会导致算法在“平均情况”的输入上表现良好，但在一些非常规输入上可能表现不佳。随机算法(有时称为“拉斯维加斯”算法)可以预期在所有输入上都表现良好， 但由于一系列不幸的抛硬币结果，其性能可能会下降。但是，这种不幸的连续抛硬币的概率通常非常小，几乎可以忽略不计。 在过去的十年中，随机采样技术在几何算法中已发展成为创建高效且简单的算法的关键技术(Mulmuley & Schwarzkopf 1997)。 我们将在第4章和第7章(4.5节、 7.5节和7.11.4节)中再次探讨这一主题。
回到Seidel的算法，我们可以在\(O(n \log n)\) 的时间和 \(O(n)\) 空间内，以随机插入线段的方式来构建可见性图，并利用它来定位每个新添加线段的端点。 这得到了一个 \(O(n \log n)\)的三角化算法。但我们还没用到一个事实，这些线段构成简单多边形。我们可以通过将算法分称 \(\log^* n\) 个阶段运行，来利用它。 在阶段 \(i\)，随机添加一部分线段，生成查询结构 \(Q_i\)。然后，通过\(Q_i\)追踪整个多边形，定位当前可见性图中梯形的每个顶点。 在阶段 \(i+1\)，添加更多线段，由于知道它们在 \(Q_i\) 中的位置，所以可以更快地定位它们的端点。重复此过程，直到构建整个可见性图。 之后我们回退到之前的技术来完成三角化。分析该算法的预期时间(针对所有可能的\(n!\)种线段插入顺序)，结果表明其复杂度为 \(O(n \log^* n)\)。此外，该算法的实现相对简单。