2.5 凸分割
(Convex Partitioning)
将一块区域划分成三角形，可以看作是划分成凸多边形的一种特殊情况。因为存在最优时间三角剖分算法，所以也存在最优时间凸多边形划分算法。但是，就凸多边形的数量而言，三角化绝非最优。
将多边形分割成凸块的目标有两个: (1) 将多边形分割成尽可能少的凸块 (2) 尽可能快地完成分割。这两个目标显然是相互冲突的。 主要有两种方法。第一种方法是在分割块的数量上做出妥协，找到一个快速的算法，但是分割块数量不是最优的。 第二种方法是在时间复杂度上做出妥协，找到分割块数最优的算法，计算效率上尽可能快速。虽然我们主要讨论第一种方法，但也会提及第二种方法的相关结果。
对多边形 \(P\) 的分割方式有两种: 对角线划分和线段划分。它们的区别在于，对角线的端点必须是顶点，而线段的端点只需位于 \(\partial P\) 上即可。 线段划分通常更复杂，因为需要计算其端点。但由于可以考虑顶点集以外的区域，因此往往能得到更高效的划分。
2.5.1. 最优分割(Optimum Partition)
为了评估划分的效率，有必要计算最佳分割的上下界。
定理 2.5.1 (Chazelle).设 \(\Phi\) 为一个多边形可分割的最少凸面片数。对于一个有 \(r\) 个反射(凹)顶点的多边形，有 \(\lceil r/2 \rceil + 1 ≤ \Phi ≤ r + 1\)。
证明:作每个反射角的角平分线，即可消除所有反射角，从而得到一个凸分割。分割后的面数为 \(r + 1\)。如图 2.10 所示。
为了形成凸分割，必须处理所有反射角。一个分割线段最多只能处理两个反射角。这会产生 \(\lceil r/2 \rceil + 1\) 个凸面。如图 2.11 所示。□
2.5.2. Hertel & Mehlhorn 算法(Hertel and Mehlhorn Algorithm)
Hertel 和 Mehlhorn(1983)发现了一种非常简洁的算法，可以用对角线快速地进行分割，并且给出了在凸块数量意义上，有多坏的边界has bounded "badness"。 对于一个多边形通过对角线进行凸分割，在顶点 \(v\) 处，如果移除对角线 \(d\) 后得到的分割区域是非凸的，那么称对角线 \(d\) 对顶点 \(v\) 是必要的。 如果 \(d\) 是必要的，那么它必定与顶点 \(v\) 相连，且顶点 \(v\) 必定是凹的。如果一个对角线，对于其两个端点都不是必要的，那么它就是非必要inessential的。
Hertel 和 Mehlhorn 的算法很简单。首先对 \(P\) 进行三角分割。然后不断地移除不必要的对角线。该算法会将 \(P\) 按对角线划分成若干凸块。 使用合适的数据结构，该算法可以在线性时间内完成(参见练习 2.5.4[4])。因此，唯一的问题是它与最优解的差距有多大。
引理 2.5.2.对于任何凹顶点，最多只能有两条对角线是必需的。
证明: 设凹顶点 \(v\) 的两个相邻顶点 \(v_+\) 和 \(v_-\)。在与边 \(vv_+\) 邻接的半平面 \(H_+\) 中，至多有一条必要对角线。 因为如果有两条，那么移除最靠近 \(v_+\) 的那条对角线也不会使得 \(v\) 变凸。如图 2.12所示。
类似地，在与边 \(vv_-\) 邻接的平面 \(H_-\) 中，也最多有一条必要对角线。这两个半平面共同覆盖了 \(v\) 处的内角，因此对于 \(v\) 而言，至多有两条必要对角线。□
引理 2.5.3.Hertel-Mehlhorn 算法在凸块数量上不会比最优算法差四倍。
证明: 当每个凹顶点的对角线都是必要的时候，终止算法。根据引理 2.5.2，每个凹顶点最多可以有两条必要的对角线。因此，必要的对角线数量最多为 \(2r\)， 其中 \(r\) 是凹顶点的数量。如果存在对角线对于其两个端点的顶点都是必要的，那么对角线的数量可以更少)。因此，算法生成的凸块数量 \(M\) 满足不等式 \(2r + 1 ≥ M\)。 根据引理 2.5.1，\(\Phi ≥ \lceil r/2 \rceil + 1 \Rightarrow 4 \Phi ≥ 2r+4 \gt 2r + 1 ≥ M\)。□
2.5.3. 最优凸分割(Optimal Convex Partitions)
找到一个在分割数上最优的凸划分比找到一个次优划分要耗时得多。第一个通过对角线实现凸分割的最优算法是由 Green(1983) 提出的。 该算法时间复杂度为 \(O(r^2 n^2) = O(n^4)\)。后来 Keil(1985) 将其改进为 \(O(r^2 n \log n) = O(n^3 \log n)\)。这两个算法都是动态规划的方法。
如果可以用任意线段进行分割，那么问题就更加困难，因为可能需要使用不与多边形边界相交的分割线段，如图 2.13 所示。 Chazelle(1980) 在他的论文中用一个复杂的 \(O(n + r^3 ) = 0 (n^3)\) 算法解决了这个问题(另外参见 Chazelle & Dobkin(1985))。
2.5.4. 练习
- 最坏情况下的分片数量Worst case number of pieces。找到一个使 Hertel-Mehlhorn(H-M) 算法出现最坏情况的通用多边形。存在一种三角分割结构，按照特定顺序移除非必要对角线， 将产生 \(2r\) 个凸块。
- 相对于最优的最坏情况Worst case with respect to optimum。找到一个通用多边形，使得 H-M 算法相对于最优解出现最坏情况。 H-M 算法生成 \(2r\) 个凸块，但实际上可以生成 \(\lceil r/2 \rceil + 1\) 个凸块。
- 更小的最优常数?Better optimality constant? 是否有可能将 H-M 算法的最优性常数降低到 4 以下? 假设对角线元素的选择更加合理，常数是否有可能达到 3?
- [Programming] 实现 Hertel-Mehlhorn 算法Implementing the Hertel-Mehlhorn algorithm。设计一种数据结构，用于存储三角分割对角线的子集， 并能够在常数时间内找到"下一个"非必要对角线。通过修改和扩展 Triangulate 函数(代码 1.14) 来实现 H-M 算法。
- [open] 更好的近似算法(对角线)Better approximate algorithm(diagonals)。找到一个最优性常数小于 4 的快速算法。其时间复杂度能达到 \(O(n \text{polylog}(n))\)， 其中 \(\text{polylog}(n)\) 是关于 \(\log n\) 的多项式，例如 \(\log^3 n\)。
- [open] 更好的近似算法(线段)Better approximate algorithm(segments)。找到一个快速的近似算法，通过线段进行分割而不是对角线。
- 分割成矩形Partition into rectangles。设计一个算法，将正交多边形(练习 2.3.4[7])分割成矩形。分割线段必须与多边形的某条边共线，且只能使用水平和垂直方向的分割线段。 设计目标是，分割成尽可能少的块，并尽快完成。
- 用矩形覆盖Cover with rectangles。设计一个算法，用边为水平和垂直的矩形覆盖正交多边形 \(P\)。每个矩形都必须位于 \(P\) 内部， 且它们的并集必须恰好等于 \(P\)。在分割任务中，矩形的内部两两互不相交。但在覆盖问题中，它们可以重叠。我们的目标是用尽可能少的矩形块，尽快完成覆盖。