2.3 单调山分割
(Partition into Monotone Mountains)
上节中描述的算法有一个更简单的变体。其思路仍然是从 \(P\) 的梯形化开始，但它不仅仅添加尖点到尖点(cusp-to-cusp)的对角线， 而是将 \(P\) 分割成若干个部分，我们称之为单调山 monotone mountains。这些形状更容易进行三角分割。
2.3.1. 单调山(Monotone Mountains)
单调山(monotone mountain)是一种单调多边形，它两条单调链中有一条仅包含一个线段，称为底边(base)。如果在水平方向上单调，那么该多边形长的就像山一样，如图 2.6 所示。 Foumier & Montuno (1984) 称这样的多边形为 unimonotone polygons。 注意，底边的两个端点都必须是凸的，否则其中一条链将包含多个线段。下面的引理会使此类多边形的三角分割变得容易。
引理 2.3.1. 单调山 \(M\) 的每个严格凸顶点都是一个耳尖。底边的端点可能是例外。
证明：设 \(a,b,c\) 是 \(M\) 中三个连续的顶点，其中 \(b\) 是一个严格凸顶点且不是底边 \(B\) 的端点。假设多边形在水平方向上单调。我们将用反证法证明 \(ac\) 是一条对角线。
如果 \(ac\) 不是对角线。那么根据引理 1.5.1，它要么在多边形之外，要么与 \(\partial M\) 相交。
- 首先假设在图 2.6 中，\(ac\) 有一部分在端点 \(a\) 邻域的外部。端点 \(c\) 的特性与之对称，无需单独考虑。
如果 \(a\) 不是 \(B\) 的端点，那么它的两条关联边分别位于 \(a\) 的左侧和右侧，\(M\) 则位于其下方。 为了使 \(ac\) 位于多边形之外，它必须局部位于 \(ab\) 的上方，这与 \(b\) 是凸的假设相矛盾。
如果 \(a\) 是 \(B\) 的右端点，则 \(ac\) 要么局部位于 \(ab\) 的上方，要么有一部分位于 \(B\) 的下方。 前者会导致与刚才一样的矛盾。后者 \(a\) 无法连接到 \(c\)，因为 \(c\) 必须位于 \(B\) 的上方。
我们可以得出结论，\(ac\) 在每个端点处都位于 \(M\) 的内部。 - 假设 \(ac\) 与 \(\partial M\) 相交。这需要存在一个凹顶点 \(x\) 位于 \(\Delta abc\) 的内部(参见图 1.12)。
由于 \(x\) 位于内部，它不可能位于链\(C = (a, b, c)\)上，也不可能位于 \(B\) 上，因为 \(B\) 只有一条线段并且端点都是凸的。
因此，过 \(x\) 的垂直线 \(L\) 至少与 \(\partial M\) 相交于三点: \(C \cap L, B \cap L\) 和 \(x\)。这与单调多边形的定义相矛盾。□
这条引理不适用于单调多边形。例如，图 2.1 中的 \(v_3\) 是凸顶点，但不是耳尖。 注意，引理的前提条件中不能移除 \(B\) 的端点，图 2.6 中的两个端点都不是耳尖。
2.3.2. 单调山的三角分割(Triangulating a Monotone Mountain)
引理 2.3.1 给出了单调山三角分割的近乎线性的算法。找到一个不在底边的凸顶点，剪掉相关的耳朵，然后重复。
要确保该算法在线性时间内结束，需要满足两个条件: (a) 在线性时间内识别出底边 (b) 无需搜索即可在常数时间内找到"下一个"凸顶点。 前者很容易实现，底边的端点是单调性方向上的极值点。如果是水平单调的，那么只需搜索最左侧和最右侧的顶点即可。一旦识别出底边，就可以在"剪耳ear-clipping"阶段避开其端点。
条件 (b) 将面临与1.4节类似的任务，剪除耳朵 \(\Delta abc\) 后更新 \(a\) 和 \(c\) 的耳尖状态。 只是这里我们需要更新的凸状态，根据引理 2.3.1，凸点就是耳尖。这可以通过存储每个顶点的内角来实现，移除 \(\Delta abc\) 时从 \(a\) 和 \(c\) 的内角中适当地减去。 然而这仍然存在一个问题。三角分割代码(代码 1.14)在一个线性时间的内循环中搜索下一个耳朵， 因为我们当时只追求 \(O(n^2)\) 的复杂度。但现在我们的目标是 \(O(n)\)。要想在无搜索的情况下找到下一个凸顶点，需要遵循练习 1.6.8[4] 的方法，将凸顶点链接到一个循环列表中， 并在每次裁剪耳朵后更新该列表。只要该列表非空，就可以立即选择其第一个元素进行每次裁剪。
下面的算法 2.2 是这种方法的伪代码:
 |
2.3.3. 添加对角线来梯形化(Adding Diagnals to Trapezoidalization)
现在我们来探讨如何将梯形化问题转化为单调山分割问题。有可能需要翻转这些单调山，使其在竖直方向上具有单调性。我们首先介绍其核心思想，然后证明其有效性。
我们要在一个特别的底边上通过梯形化来构建一个单调山，比如如图 2.7 中的 \(B = v_{11}v_{12}\)。 我们用符号 \(T(i, j)\) 表示由顶点 \(v_i\) 和 \(v_j\) 支撑的梯形，它们分别位于梯形的下方和上方。\(T (12, 2)\) 就以 \(B\) 为底边， 但需要由对角线 \(v_{12}v_2\) 切割，才能保证端点 \(v_{12}\) 是凸的。\(T(2, 3)\) 和 \(T(3, 4)\) 可以完整地包含在内。 \(T(4, 6)\) 需要对角线 \(v_4v_6\) 切割，以分离 \(v_6\) 处的非单调性，类似地，\(T(6, 8)\) 需要由 \(v_6 v_8\) 切割。 最后，\(T(8, 11)\) 必须被 \(v_8 v_{11}\) 切割，以保证顶点 \(v_{11}\) 是凸的。如此所得的多边形(\(v_{11}v_{12} v_2 v_3 v_4 v_6 v_8\))就是一个单调山。
注意，我们要沿着梯形的两个支撑顶点之间的对角线切割梯形。这正是两个支撑顶点不同时位于梯形的同一侧斜边上的情况。 这引出了以下引理：
引理 2.3.2. 在多边形 \(P\) 的梯形化过程中，连接每个梯形不同侧的支撑顶点，就可以将 \(P\) 分割成单调山monotone mountains。
证明：这些分割块一定是单调的，因为内部尖点既不位于它所支撑的梯形的左侧也不位于右侧，所以它总是被当做对角线的端点。 We may observe at once that the pieces must be monotone, because an interior cusp does not lie on either the left or the right side of the trapezoid it supports, so it is always the endpoint of a diagonal that resolves it. 说实话我没有理解这句话的因果关系在哪里，大概是想说这些分割块不存在内部尖点。 引理 2.1.1保证了分割块的单调性。接下来我们需要证明每个分割块都包含一条由单个线段构成的链。
假设相反的情况，存在切块 \(Q\) 的两个单调链 \(A\) 和 \(B\) 都至少包含两条边。设 \(z\) 是 \(Q\) 的最顶端顶点，在 \(\partial Q = A \cup B\) 上与顶点 \(a \in A\) 和 \(b \in B\) 相邻， 并且 b 位于 a 的下方。参见图 2.8。为了使 \(B\) 包含的边不止 \(zb\)，那么 \(b\) 就不能是分割对角线的端点。考虑由顶点 \(b\) 从下方支撑的梯形 \(T(b, c)\)。 它的上支撑顶点 \(c\) 不能位于 \(zb\) 上，因为 \(c\) 必须位于 \(a\) 处或 \(a\) 的下方。因此，在 \(T(b, c)\) 中 \(b\) 与 \(c\) 不会在同一侧，对角线 \(cb\) 包含在 \(Q\) 中， 这与 \(B\) 延伸到 \(b\) 下方的假设相矛盾。□
图 2.7 展示了将此引理应用于图 2.3 的结果。 为了实现更精细的分割，还需要三条对角线，从而得到八座单调山峰，而之前只有五块单调的山峰。
现在我们基本上得到了第二个 \(O(n \log n)\) 的三角分割算法。在梯形化之后，根据引理 2.3.2 添加对角线，再使用算法 2.2 对每个部分进行三角剖分。 我们将设计数据结构以实现单调山的有效提取的任务留给练习 2.3.4[4]。
2.3.4. 练习
- 单调对偶Monotone duals。证明每个二叉树都可以实现为一个单调山的三角分割对偶。(参考习题 1.2.5[2])
- [Programming]随机单调山Random monotone mountains。编写代码生成"随机"单调山。 按照自然意义上的"随机"，生成随机多边形是一个开放性问题，但单调山的特殊性使得这个问题变得容易一些。
- [Programming]三角化单调山Triangulating monotone mountains。实现算法 2.2。
- 梯形数据结构Triangulating data structure。设计一个数据结构，用于对多边形 \(P\) 进行梯形化，并添加一组对角线，从而能在与子多边形大小成正比的时间内提取出所得划分的子多边形。
- 多边形 \(\Rightarrow\) 凸四边形Polygon \(\Rightarrow\) Convex quadrilaterals。证明或正反，每个有偶数个顶点的多边形都可以用对角线分割成凸四边形。
- 多边形 \(\Rightarrow\) 四边形Polygon \(\Rightarrow\) Quadrilaterals。证明或正反，每个有偶数个顶点的多边形都可以用对角线分割成四边形。
- 正交金字塔 \(\Rightarrow\) 凸四边形Orthogonal pyramid \(\Rightarrow\) Convex quadrilaterals。
正交多边形是指每对相邻边都互相垂直的多边形(练习 1.2.5[5])。不失一般性，我们可以假设这些边水平和垂直交替出现。
正交金字塔(orthogonal pyramid) \(P\) 是一个关于竖直方向单调的正交多边形，它包含一条水平边 \(h\)，该水平边的长度等于所有其他水平边的长度之和。 因此 \(P\) 在竖直和水平方向都是单调的。实际在水平方向上，它是一座单调的山。如图 2.9 所示，\(P\) 由两个连接到水平边 \(h\) 的"阶梯"组成。
a. 证明正交金字塔可以被对角线分割成凸四边形。
b. 设计一个算法来寻找这样的划分。尽量实现线性时间复杂度。用伪代码简要描述你的算法，忽略数据结构细节和操作。 - 正交多边形 \(\Rightarrow\) 凸四边形Orthogonal polygon \(\Rightarrow\) Convex quadrilaterals。每个正交多边形都能被对角线分割成凸四边形吗？深入探讨这个问题，并形成一个猜想。
