2.1 单调多边形分割
Monotone Partitioning

我们在 1.4 节中给出了一个 \(O(n²)\) 的三角分割算法。 进一步的改进需要更智慧地组织计算，以便在亚线性(sublinear)时间内找到每条对角线。 现在有很多算法可以达到 \(O(n \log n)\) 的时间复杂度，查找对角线的平均复杂度为 \(O(1 \log n)\)。第一个这样的算法是由 Garey, Johnson, Preparata 和 Tarjan (1978) 提出的。 人们可能会以为一个 \(O(n \log n)\) 的算法可以通过 \(O(log n)\) 的二分查找来找到每条对角线，但实际上他们的算法并非如此。 他们首先用 \(O(n \log n)\) 的时间复杂度将多边形分割成更简单的小块，然后以线性时间复杂度对这些小块进行三角分割。 这些小块被称为"单调(monotone)多边形"，这个概念最初由 Lee 和 Preparata (1977) 提出并加以利用的。将多边形分割成单调多边形，除了用于三角分割之外还有其他用途，因此值得探索一番。

我们将仅概述复杂度为 \(O(n\log n)\) 的单调分割算法，但会在第 2.3 节回来将详细介绍一个与之密切相关的，基于"单调山(monotone mountains)"的算法。

我们首先定义单调性(monotonicity)，然后展示如何在线性时间内对单调多边形进行三角分割，最后描述如何将多边形分割成若干单调多边形。

2.1.1. 单调多边形 (Monotone Polygons)

单调性是相对于一条直线定义的。首先，我们定义多边形链(polygonal chains)的单调性。对于一个多边形链 \(C\) 和直线 \(L'\)， 如果每一个垂直于 \(L'\) 的直线 \(L\) 都与 \(C\) 最多有一个交点，即 \(L \cap C\) 要么是空集，要么只有一个点。那么我们称 \(C\) 是严格单调的(strictly monotone)。 如果 \(L \cap C\) 最多只有一个连通部分，即 \(L \cap C\) 要么是空集，要么只有一个点，要么是一条线段。那么它就是单调的。 这些链之所以是"单调的"，是因为遍历 \(C\) 在直线 \(L'\) 上的投影是一个单调序列，没有出现反转(no reversals occur)。

如果多边形 \(P\) 的边界 \(\partial P\) 可以被分割成两条多边形链 \(A\) 和 \(B\)，且每条链都关于直线 \(L\) 单调，那么我们称多边形 \(P\) 关于直线 \(L\) 单调。 两条链的首尾各共用一个顶点。图 2.1 展示了一个关于垂直方向单调的多边形。图中两条单调链分别为 \(A = (v_0, \cdots, v_{15})\) 和 \(B = (v_{15}, \cdots, v_{24}, v_0)\)。 这两条链都不是严格单调的，因为边 \(v_5v_6\) 和 \(V_{21}V_{22}\) 是水平的。有些多边形可能会关于多条直线单调，而有些多边形可能关于任何直线都不是单调的。

单调多边形的性质

许多对一般多边形来说很困难的算法，对单调多边形来说却很容易。这主要是因为单调多边形具有以下关键特性: 单调多边形的每条链中的顶点都是相对一条直线单调排序的。 假设单调线是垂直于 \(y\) 轴的，那么顶点就可以在线性时间内按 \(y\) 坐标排序: 先找到最高点和最低点，然后将边界分割成两条链。 这两条链中的顶点都是按照 \(y\) 坐标排序的。我们也可以在线性时间内，合并两条已排序的顶点列表，生成一个按 \(y\) 坐标排序的顶点列表。

单调性可以用一个简单的局部结构特征来表示。如果一个多边形每个顶点的邻居都是单调的，那么这个多边形就是单调的。 这是该算法的基础，通过在局部非单调区域进行切割，将多边形分割成单调的部分。

如果一个顶点 \(v\) 是凹的，其相邻顶点 \(v_{-}\) 和 \(v_{+}\) 要么都不高于 \(v\)，要么都不低于 \(v\)，那么 \(v\) 就是多边形的内尖点(interior cusp\)。 参见图 2.2。凹顶点的内角都大于 \(\pi\)，因此内尖点的两个邻居顶点的 \(y\) 坐标，不可能同时都与 \(v\) 的相等。 因此，图 2.2(b) 中的点 \(d\) 就不是内尖点。内特征可以用以下简单的引理来描述。

尽管这个引理很直观，但证明它还是不容易的Lee & Preparata (1977) or O'Rourke (1994, pp. 54-5)。 可能不是那么直接，这个引理不能被拓展为: 缺少内部尖点意味着严格单调性(练习 2.2.3[2])。我们不证明这个引理，将在 2.2 节中利用这个引理将多边形分割成单调的部分。

2.1.2. 三角化单调多边形 (Triangulating Monotone Polygon)

由于单调多边形的约束很强，人们期望它的三角分割也会有一些特殊的性质，比如，它的三角分割的对偶图总是一条路径，每个对角线都会连接两个单调链。 如图 2.1 所示，这两个假设都不成立，另见练习 2.3.4[1]。然而这些形状非常特殊，因此直觉上很容易认为对它们进行三角分割会很容易的。 人们期望，任何单调多边形(其单调方向已知)都可以在线性时间内进行三角分割。

有一种算法，首先将顶点从上到下排序(线性时间复杂度)。然后"贪心"地从顶部切出三角形。贪心 greedy是一个算法术语，在此表示每一步都移除第一个可用的三角形。 其计算过程为，对于每个顶点 \(v\)，将 \(v\) 与其上方所有可见的顶点通过对角线连接起来，并移除由此三角化的多边形的顶部部分，然后继续处理 \(v\) 下方的下一个顶点。

可以证明在每次迭代中，顶点 \(v \in A\) 都与另一条链 \(B\) 中位于其上方的凹顶点链相连。例如，在图 2.1 的示例中，顶点 \(v_{16}\) 在第一次迭代中与顶点 \(v_{14},v_{13},v_{12}\) 相连。 因此，无需进行可见性检查即可确定这些对角线，它们可以立即输出。该算法可以用一个存储上方凹链的栈来实现。由于采用了线性排序和这种简单的数据结构，其总时间复杂度为 \(0(n)\)。