[论文解析] Hu-Shing 算法 - 快速求出矩阵链乘积最优解

tiger2005 · 2024-03-11 22:22:31 · 算法·理论

论文 Part I | 论文 Part II | 论文另版 | 模板

本文中所有图片均来自原论文。

Chpt. 1 简要介绍

Hu-Shing 算法，是一个能够快速解决矩阵链乘积（或矩阵链排序问题，MCOP）的算法。在这项研究成果之前，A. K. Chandra 就已经提出在 O(n) 的时间复杂度下计算处近似解的算法（具体而言，近似解的代价不超过最优解代价的两倍），而这一算法被 F. Y. Chin 进一步优化，在同样的时间复杂度内达到了更高的精确度。而在该论文中，两人提出了一个在 O(n \log n) 的时间复杂度下计算精确解的算法，并将论文分为两部分，分别在 1982 年和 1984 年发出。值得说明的是，文章的开头给出了三个链接，其中前两个是较为正式化的论文，而第三个包含比较详细的证明过程。

下面是对 MCOP 的介绍。

下式将 n - 1 个矩阵相乘，并最终得到一个新的矩阵：

M = M_1 \times M_2 \times \cdots \times M_{n-1}

我们假设 M_i 是一个 w_{i} \times w_{i + 1} 大小的矩阵。考虑到矩阵乘法满足结合律，那么我们任意改变乘法的顺序，所得到的最终矩阵必然是相同的，但运算次数却不尽相同。该问题的目的是找到一个最优的乘法策略，满足在该策略下进行矩阵乘法所需操作数最少。在这里，我们假设对 p \times q 的矩阵和 q \times r 的矩阵进行乘法所需的操作数是 pqr。

在接下来的解析中，我们将 Part I 提到的引理、公理和推论加上 "1." 的前缀，而将 Part II 提到的引理、公理和推论加上 2." 的前缀。

Chpt. 2 划分凸多边形

对于一个包含 n 个节点的凸多边形（下简称 n 边形），我们可以在其内部将两个不相邻的节点以线段相连（在之后，我们称这类线段为弧）。在连接了 n-3 条互相不在中间相交的弧后，我们就将这个凸多边形分成了 n-2 个三角形（我们称这样的方案为划分），而对应的方案数就是卡特兰数。我们给每个节点设立一个权值 w_i，并按照如下方式计算一个划分的代价：

• 对划分出的每个三角形，不妨假设其连接了权值分别为 x, y, z 的三个节点，那么其代价为 xyz。
• 一个划分的代价就是所有三角形的代价和。

在上面对六边形的划分中，对应的代价就是

我们称一个凸多边形的划分为最优划分，当且仅当这个划分提供了最小的代价。

在上面的例子中，我们将 V_1 - V_6 的边作为基底，其象征着矩阵乘法的最终结果 M。而如果我们按照顺时针顺序考虑多边形上的每条边，就可以发现它们实际上按顺序对应了被乘的 n-1 个矩阵的大小。接下来，我们将通过一个引理，将矩阵乘法的问题转换到凸多边形的划分问题上。

引理 1.1：对 n-1 个矩阵的链式乘法分配方案都可以对应到 n 边形的一个划分。

证明：考察最后一次乘法的位置：

考虑到这一次乘法实际上是将一个 w_1 \times w_{p} 的矩阵和 w_{p} \times w_n 的矩阵相乘，那么我们在一个凸多边形上添加 V_1 - V_{p} 和 V_{p} - V_{n} 两条弧。这两条弧和基底共同围成的三角形提供的代价恰好等于最后一次乘法所需的操作次数。

进一步的，为了得到乘法左右的两个矩阵，我们可以继续考虑这两个矩阵进行的最后一次乘法，而这恰好对应三角形左右的两个子多边形（它们的基底也分别对应了我们此时连接的两条边）。我们就可以利用归纳法的思路，继续将这个凸多边形进行等代价的划分，直到剩下的部分无法再划分，矩阵不断退化为初始给出的矩阵为止。

此时，我们就通过乘法的结合方式推出了凸多边形的一种划分。这也就说明了每一种乘法结合方式对应了一种划分。

在链式乘法到划分的转化下，我们可以立马得到另一个引理：

引理 1.2：引入一个大小为 w_n \times w_1 的矩阵 M_n，那么对下面所有的矩阵链式乘法所需的最少操作次数相同：

M_1 \times M_2 \times \cdots \times M_{n-1}\\ M_n \times M_1 \times \cdots \times M_{n-2}\\ \vdots\\ M_{2} \times M_{3} \times \cdots \times M_n

证明：对于上述的矩阵链式乘法，在实质上对应的是同一个凸多边形的最优划分代价，那么它们对应的最少操作次数必然相同。

在正式步入划分问题之前，我们需要补充一个事实。对于凸多边形的任何一个划分，我们必然可以逐步将二度点（恰好与两条边相连的点）连带着它所连的边一起删除，并在最后留下基底对应的线段。在这个过程中，我们可以注意到：每一次移除实际上对应了一次矩阵乘法，而每一次移除后剩余的凸多边形，除了基底之外的边都分别对应了当前链式乘法中每个矩阵的对应大小。我们就通过模拟的方式将划分对应到了链式乘法的一种组合方式。

接下来，我们考虑通过一个引理侧面反映上述操作的可行性。

引理 1.3：在 n 边形（n \geq 4）的任意划分中，必然存在至少两个包含二度点的三角形。

证明：我们通过 n-3 条弧和 n 条侧边围出了 n-2 个互不相交的三角形，而由于 n \geq 4，那么其中任何一个三角形都无法由三条侧边围出。我们假设：

那么我们有

由于 z \geq 0，显然有 x \geq 2。而考虑到每个由两条边和一条弧组成的三角形必然有一个二度点，那么我们就证明了这个引理。

至此，我们终于完成了矩阵链式乘法问题到多边形划分的问题，也终于可以将全部精力集中在解决新的图论问题上了。

我们首先补充第一个记号：C(w_1, w_2, \cdots, w_k)，其对应以 \{w_i\} 作为点权的 k 边形对应的最优划分代价。我们立马给出一个引理。

引理 1.4：如果 \forall i \in [1, k], w_i \leq w'_i，那么

C(w_1, w_2, \cdots, w_k) \leq C(w'_1, w'_2, \cdots, w'_k)

证明在此略去。

然后，我们继续对图论记号进行扩充。

在后续对图的讨论中，侧边被用来强调凸多边形外部的线段，而弧被用来强调凸多边形内部的线段。

称两个点在凸多边形相邻，当且仅当二者之间连有一条侧边。称两个点在凸多边形相连，当且仅当二者之间连有一条边。

在剩余的篇幅中，我们需要将点重新标记。我们使用 V_1, V_2, \cdots, V_n 表示按照权重排序的点序，也就是说，此时有 w_1 \leq w_2 \leq \cdots \leq w_n。对于 w_i 相等的一些点，我们随便选择一个点并从该点开始顺时针行动，将沿途所有权值等于 w_i 的点依次记录。另外定义 T_{ijk} = w_i \times w_j \times w_k。

接下来定义 V_i < V_j，当且仅当 i < j。这个定义自然蕴含了 w_i \leq w_j。我们另外定义一个多边形的最小点为小于其他所有点的点。

在每个点都被标记之后，我们就可以定义边的顺序了。定义边 V_i - V_j 小于边 V_k - V_l，当且仅当

据此，我们可以定义：一个划分 P 字典序小于 划分 Q，当且仅当在将各自的弧从小到大排序后，P 形成的弧排列字典序比 Q 小。在这一条件下，我们定义 最小最优划分为所有最优划分中字典序最小的一个。

接下来，我们将给出一个十分重要的定理。

定理 1.1：对于任何一种排列 V_1, V_2, \cdots, V_n 的方式，我们总能找到一种最优划分，其包含 V_1 - V_2 和 V_2 - V_3 两条边（可以是侧边或者弧）。

证明：尝试对凸多边形的大小进行归纳。对于三边形和四边形而言，这个结论是正确的。接下来，令 n \geq 5，并假设对所有 3 \leq k \leq n - 1，这个结论在 k 边形上均正确，然后对 n 边形进行讨论。

根据引理 1.3，这个凸多边形上必然存在两个二度点，假设为 V_i 和 V_j。我们将讨论分为两部分。

• 如果 V_i 不是 V_1, V_2, V_3 中的一个，那么考虑直接将 V_i 所在的三角形移走，那么在剩余的 n-1 边形中，V_1, V_2, V_3 依然分别是最小的三个点。根据前提，必然存在 V_1 - V_2 和 V_2 - V_3 两条边。对 V_j 同理。

• 如果 V_i 和 V_j 都在 V_1, V_2, V_3 中。我们假设 V_i < V_j，那么其对应三种情况：

  • $$ T_{12q} + C(w_2, w_q, \cdots, w_p, w_3) $$ 而如果直接连接 $V_1 - V_3$，代价为 $$ T_{123} + C(w_1, w_q, \cdots, w_p, w_3) $$ 根据定义，$T_{123} \leq T_{12q}$，而根据引理 1.3，$C(w_1, w_q, \cdots, w_p, w_3) \leq C(w_2, w_q, \cdots, w_p, w_3)$。那么连接 $V_1$ 和 $V_3$ 显然是更优的选择。

我们就证明了这个定理。

推论 1.1：对于任何一种排列 V_1, V_2, \cdots, V_n 的方式，最小最优划分必然包含 V_1 - V_2 和 V_1 - V_3 两条边。

证明在此略去。

在这个定理的帮助下，我们可以尝试递归解决原先的问题。对于一个多边形，只要 V_1 - V_2 或者 V_2 - V_3 是一个弧，我们就可以将这个多边形分成若干个子多边形。这个过程将一直持续到 V_1 分别和 V_2, V_3 相邻，此时该递归无效。

称一个多边形为基础多边形，当且仅当其包含至少四个点，并且 V_1 和 V_2, V_3 相邻。在之后的定理中需要时刻注意多边形的类型。

接下来，我们通过一个定理论述对基础多边形的处理方式。

定理 1.2：在一个基础多边形中，V_2 - V_3 在一个最优划分中存在的一个必要而不充分的条件是

\dfrac 1 {w_1} + \dfrac 1 {w_4} \leq \dfrac 1 {w_2} + \dfrac 1 {w_3}

另外，在最小最优划分中，如果 V_2 - V_3 不存在，那么 V_1 - V_4 必然存在。

证明：在最小最优划分中，如果 V_2 - V_3 不存在，那么 V_1 的度数至少为 3，假设 V_1 和 V_p 连有一条弧，并将原多边形分成两个子多边形，那么考虑在两个子多边形中，必然有至少一个子多边形，其第三小的点是 V_4。那么此时根据推论 1.1，V_1 - V_4 必然存在。

如果在一个最优划分中，V_2 与 V_3 相连，那么考虑移除 V_1，在新的多边形中，根据定理 1.1，V_2 和 V_4 需要相连。如果这条边是一条弧，那么我们可以继续递归下去解决子问题。现在考虑假设 V_4 和 V_2 相邻。

考虑上图中两种情况的代价。左侧构造的代价是

右侧构造的代价是

首先，根据引理 1.4，我们知道 C(w_2, w_4, \cdots, w_3) > C(w_1, w_4, \cdots, w_3)。而考虑到二者中只有一个权值发生了变化，那么我们知道 C(w_2, w_4, \cdots, w_3) - C(w_1, w_4, \cdots, w_3) 应当至少为 T_{234} - T_{134}。

为了使左侧不劣于右侧，我们可以得到一个更加宽松的不等式

也就是

我们紧接着给出一个引理。这个引理来自最经典的调整思路。

引理 1.5：在一个最优划分中，假设 V_x - V_z 是一条弧，与其相邻的两个三角形分别暴汗了 V_y 和 V_w（也就是说，V_x - V_y - V_z - V_w 共同形成了一个四边形），那么选择 V_x - V_z 而非 V_y - V_w 的必要条件是

\dfrac 1 {v_x} + \dfrac 1 {v_z} \geq \dfrac 1 {v_y} + \dfrac 1 {v_w}

证明：考虑此四边形，连接 V_x - V_z 的代价是

而连接 V_y - V_w 的代价是

为了保证前者不劣于后者，我们有

也就是

值得注意的是，如果上述不等式无法取等，那么 V_x - V_z 是必需相连的。而如果能够取等，那么两条边中字典序较小的边必然会出现在最小最优划分中。

如果所有弧都满足上述性质，那么称该划分是稳定的，因为我们无法简单的通过四边形内的调整进行优化。

推论 1.2 最优划分一定是稳定的，而稳定的划分不一定是最优的。

证明：前半部分显然，而对后半部分，可以给出反例。

值得注意的是，引理 1.5 得到的不等式实际上可以进一步弱化，并拆分成两种形式。

称一个弧 V_x - V_z 为竖直的（称其为竖直弧），当且仅当

称一个弧 V_x - V_z 为水平的（称其为水平弧），当且仅当

推论 1.3：所有的弧要么水平，要么竖直。

证明：不妨假设有一个弧 V_x - V_z 既不水平又不竖直。那么其满足两种情况

不难发现，两种情况均违背了引理 1.5 给出的不等式，故这一条弧不可能存在。

在接下来的定理中，我们将目光聚焦在水平弧上。

定理 1.3：对于多边形上任意的两个不相邻的点 V_x, V_z，不妨假设 V_y 是在 V_x - V_z 一侧的点中最小的一个，而 V_w 是在另一侧的点中最小的一个。方便起见，假设 V_x < V_z, V_y < V_w。那么在最小最优划分中，V_x - V_z 作为水平弧存在的必要条件是

w_y < w_x \leq w_z < w_w

证明：利用反证法。如果 w_x \leq w_y，可知 w_x 比其他所有点的权值都要小，也就是 w_x = w_1。在此情况下水平弧的要求必然不会被满足。因此我们必然有 w_y < w_x \leq w_z。此时 V_y 成了最小的一个点，也就是 V_y = V_1。

假设有 V_3 < V_x < V_z。根据推论 1.1，此时 V_1 - V_2 和 V_1 - V_3 均存在，并将原多边形分成若干个子多边形。如果此时 V_x 和 V_z 被分开，那么这个弧就无法形成。否则，我们选择同时包含二者的子多边形继续递归。这个过程可以一直进行到状态为基础多边形的时刻。

在这个基础多边形中，根据定理 1.2，必然有 V_2 - V_3 存在或者 V_1 - V_4 存在。如果 V_2 - V_3 存在，那么我们显然可以将 V_1 扔掉（因为此时 V_1 是二度点），然后在新的多边形中重新令 V'_1 = V_2 并递归。否则，如果 V_1 - V_4 存在，那么这条弧会继续把整个多边形分下去。因此，不断分割的过程将会一直持续到两个状态：

根据定理 1.2，我们可以得到该弧存在的必要条件：

由于 w_m < w_x，我们可以推出 w_z > w_w。

推论 1.4：将上述定理进行弱化后，可以得到水平弧在最小最优分划存在的必要条件是：

V_y < V_x < V_z < V_w

证明在此略去。

实际上，上面的推论有一个更加直观的解释。对于一个水平弧，若想让这个弧出现在最小最优分划中，那么该弧一侧的所有点都要同时大于两个端点，而另一侧需要存在一个点同时小于两个端点。我们称前者形成的子多边形为上多边形，而后者为下多边形。

我们称满足上述性质的弧为潜在水平弧。显然，最小最优分划中的所有水平弧只会是潜在水平弧。

我们在此给出一个新的推论。

推论 1.5：对于一个多边形的最大点 V_m，令 V_x, V_z 与这个点相邻，那么如果存在一个 V_y 使得 V_y < V_x 并且 V_y < V_z，那么 V_x - V_z 就是一个潜在水平弧。

证明在此略去。

接下来，我们引入兼容的概念。称两个弧互相兼容，当且仅当二者可以在一个划分中同时出现——换句话说，二者不会在非端点处相交。接下来，我们将会提出论文 Part I 中最为重要，也是最漂亮的定理。

定理 1.4：所有的潜在水平弧两两互相兼容。

证明：利用反证法。假设 V_x - V_z 是一个潜在水平弧，并沿用定理 1.3 的相关假设。我们知道 V_y < V_x < V_z < V_w。接下来，假设有一个潜在水平弧 V_p - V_q 与之相交，则两个端点必然落在 V_x - V_z 的两侧，这里假设 V_p 和 V_y 在同一侧。

根据定义，我们有 V_x < V_z < V_w \leq V_q。而注意到 V_p - V_q 需要满足一侧的所有点大于 V_q，但是 V_x 和 V_z 却同时小于 V_q，造成矛盾。故不存在互不兼容的潜在水平弧。

至此，Part I 中的全部理论准备都已经证完。根据推论 1.4 和定理 1.4，我们可以给出基于栈实现 O(n) 寻找潜在水平弧的算法。原文的算法考虑并不周全，故在此处重新实现了算法的具体流程。

我们任意选择一个权重最小的位置作为 V_1（在原论文的 Part II 开头证明了这种任意性是正确的）。从 V_1 开始，沿着顺时针方向游走，每到达一个点就尝试将其权重加入到栈中。此时的栈实际上维护了目前凸多边形的一部分外轮廓。

假设栈顶元素为 V_t，而第二个元素是 V_{t-1}。当我们尝试把 V_c 压入栈中的时候，只要栈内还有至少两个元素，并且 w_t > w_c，我们就把 V_c - V_{t-1} 列为潜在水平弧并弹出 V_t。持续这个过程直到无法弹出新元素之后，我们再把 V_c 压入栈。显然，这个栈实际上是一个单调栈。

在枚举完成后，如果栈中存在至少四个元素，那么直接把 V_c - V_{t-1} 列为潜在水平弧并弹出 V_t。持续这个操作使得整个栈存在不超过三个元素。

由于整个过程只需要绕着多边形走一圈，那么称这个算法为“单次扫描算法”。这个算法没有直接对点进行重标号，所以相对编号是比较灵活的，同时也避免了排序的复杂度。

另外，这个算法产生的弧序列实际上只保证包含所有的潜在水平弧，而其中也会包含其余不符合条件的弧（实际上，这些弧恰好是所有和 V_1 相连的弧），故在算法后需要进行筛选。但可以保证的是，整个算法将会给我们提供 n-3 条弧。

实际上，原论文给出的算法可以进一步优化，参考后续的示例代码。

Chpt. 3 单调基础多边形

我们终于迈入了该论文的 Part II。这一部分和下一部分将会完整的阐释最终的算法是如何运作的。

在此之前，我们需要解决一个子问题：单调多边形。我们首先扩充一些定义。

定义一个点是局部最大值，当且仅当它大于两个与它相邻的点。同理定义局部最小值。

定义一个多边形是单调多边形，当且仅当其恰好包含一个局部最大值和一个局部最小值。更具体的，我们只需要讨论单调基础多边形的情况。

另外，我们引入一个比较形象的划分形式。我们假设所有和最小的点不相邻的点都和最小的点连一条弧，那么我们就得到了一个类似于扇形的划分。我们将这种划分记作

并称最小点 V_1 为这个扇形划分的中心。这个定义也可以轻松转移到子多边形上。

我们引出 Part II 的第一个引理。

引理 2.1：对于一个不存在潜在水平弧的多边形，最小最优划分必然是扇形划分。

证明：显然，此时的最优划分只能由竖直弧组成。那么扇形划分显然满足竖直弧的性质，并且也是理论上能够达到的最小字典序。

接下来假设有一个更优的划分，其并不是扇形划分。那么必然存在三个点 V_i, V_j, V_k，使得划分中存在三角形 V_1V_iV_j 和 V_iV_jV_k。此时在 V_1 - V_i - V_j - V_k 中检验，根据假设，V_i - V_j 是竖直弧，我们可以知道 w_1 = \min(w_i, w_j), \max(w_i, w_j) \leq w_k。因此，根据引理 1.5，我们发现将 A_i - A_j 这条边转移到 A_1 - A_k 实际上不劣，而且字典序更小，这自然违反了一开始的假设。

还记得前面定义的上多边形吗？我们在这里需要借助上多边形定义潜在水平边的层级关系。定义一条潜在水平弧 V_p - V_q 在另一个潜在水平弧 V_i - V_j 之上，当切仅当 V_i - V_j 的上多边形包含了 V_p - V_q 这条边。

我们定义 P 为单调基础多边形的所有潜在水平弧的集合，可以清楚 P 的大小不超过 n - 3。

引理 2.2：在集合 P 中，两条潜在水平弧之间不存在互相包含或者互相不包含的关系。

证明：由于两条潜在水平弧不能互相交叉，所以它们的上多边形必然是包含关系。而考虑到在单调基础多边形中，任何一个潜在水平弧的上多边形必然包含唯一的一个局部最大值，则上多边形的交不可能为空。

根据上述性质，我们自然得到了证明。

在上述引理的帮助下，我们就可以大致刻画出潜在水平弧的位置关系。

我们将最大值提到上方，而最小值拉到下方，整体就形成了一个竖直的结构。潜在水平弧横跨竖直结构的左右两侧，并且形成一个层状结构。

进一步的，假如 V_p - V_q 在 V_i - V_j 的上方，根据上多边形的性质，我们有 \min(v_p, v_q) \geq \max(w_i, w_j)。

同时，我们定义 V_j - V_i - \cdots - V_p - V_q - \cdots - V_j 形成的多边形为“以 V_p - V_q 为上边沿，V_i - V_j 为下边沿约束形成的多边形”，或者进一步称作“被 V_p - V_q 和 V_i - V_j 约束的多边形”。

引理 2.3：在单调基础多边形中，任何一个被两条潜在水平弧约束的子多边形必然是一个单调基础多边形。

证明：考虑到单调基础多边形两侧点之间的单调性，可以证明无论两条潜在水平弧的两个端点的大小如何，我们总能确认出恰好一个局部最大值和一个局部最小值。

引理 2.4：在单调基础多边形中，对于任何一个被两条潜在水平弧约束的子多边形，其自身的潜在水平弧在整个多边形中依然是潜在水平弧。

证明：分别考察上多边形和下多边形的性质，可以发现潜在水平弧的上多边形在加入比两个端点大的一系列点，并且在下多边形中加入任意的点，都不会影响潜在水平弧的性质，故该性质可以延续到整个多边形上。

为了方便起见，我们在这里假设最大的点和最小的点等价于两个退化的潜在水平弧，那么我们可以大致清楚最终的最小最优划分的结构：整个多边形被一些潜在水平弧拆分称若干部分，而每一部分都被两个潜在水平弧约束，并且都使用扇形划分。

对于所有可能的潜在水平弧选择方案，我们将它们以包含的潜在水平弧的条数作为关键字分为 H_0, H_1, \cdots, H_{n-3} 的组，其中 H_0 包含的划分不包含潜在水平弧，H_1 包含的划分恰好包含一条潜在水平弧，以此类推。

对于 H_0 而言，其显然只包含一种划分：

对于 H_1 而言，我们只要确认其中划分包含哪个潜在水平弧，我们也可以快速得到这个划分的具体信息（只需要把分出来的两个子多边形应用扇形划分即可）。

对于一个扇形 \text{Fan}(w_i|w_j, \cdots, w_k) ，我们知道 V_i 连向了 V_j - V_k 分成的两侧中不包含 V_1 的一侧中的所有点都连了一个竖直弧。假设 V_j 和 V_k 之间按顺序包含 V_p, V_q, V_r 三个点，那么我们可以写出这个扇形结构的代价：

这里，我们利用 (w_j : w_k) 概括了“相邻两个点乘积之和”部分的内容。可以写出 H_0 对应的最小代价

我们假设在 H_i \space (i \geq 1) 包含的所有划分中的最小最优划分只包含一条潜在水平边 V_c - V_d。我们额外定义 C(w_c : w_d) 代表 V_c - V_d 对应的上多边形的最小代价，那么这个划分比直接利用扇形划分更优，当且仅当

这个式子可以直接用于衡量一个潜在水平弧的贡献能力。在一个多边形中，我们称一个潜在水平弧是正贡献的当且仅当上述不等式成立，否则称其为负贡献的。当然，这个定义也可以迁移到子多边形上，只需要强调 (w_c : w_d) 记号包含的点对，并且将 w_1 换成子多边形的最小权重即可。

在上述过程中，我们注意到正贡献的判定公式左右已经将子多边形的上边沿和下边沿独立了出来：

• 不等式左侧 \dfrac{C(w_i : w_j)}{(w_i:w_j) - w_i w_j} 的形式只和子多边形的上边沿相关，而且上边沿越高，对应的值也越大；
• 不等式右侧 w_1 的形式恰好等于子多边形下边沿的两个端点中较小者的权值，同样的，下边沿越低，对应的值越小。

接下来，我们用 h_a, h_b 等类似形式表示潜在水平弧，并且假设 h_a 的两个端点为 V_a < V'_a，并不失一般性地将所有较小点固定在单调多边形的一侧。为了方便起见，将局部最大点视为 h_n，将局部最小点视为 h_1。

我们将不等式左侧的表达式进行特化，用 S(h_c/h_i) 表示固定 h_c 作为上边沿，考察 h_i 的正贡献时不等式左侧的值（下面称为支持系数），也就是 \dfrac{C(w_i, \cdots, w_c, w'_c, \cdots w_i')}{(w_i:w'_i) - w_i w'_i}。

接下来论述一个性质。假设 h_j 在被 h_k 和 h_i 约束出的多边形中其正贡献，由于其必然存在于这个多边形的最优划分中，我们知道上多边形的最小代价和下多边形的最小代价之和恰好等于整个多边形的最小代价（C 函数值可加）。当我们进一步观察支持系数的分母，就可以发现其在任意时刻同时满足这个可加性。也就是说， S(h_k/h_i) 的分子分母可以直接由 S(h_k/h_j) 和 S(h_j/h_i) 对应的分子分母相加而来，根据经典不等式，这个支持系数也必然在原先的两个支持系数之间。

在这个性质的帮助下，我们不妨考虑正贡献的性质能否从外向内延续。

定理 2.1：如果潜在水平弧在某个多边形中为正贡献的，那么它在任意一个包含自身的子多边形中也是正贡献的（前提是不能变成侧边），反之则不然。

证明：仍然选择一条潜在水平弧 V_{i} - V_{j}，其在整个多边形为正贡献当且仅当

而如果我们只考虑一个包含 V_i - V_j 的子多边形，令其上边沿为 h_c，那么其在这个子多边形上为正贡献当且仅当

根据单调基础多边形的性质，我们知道 w_m \geq w_1。左侧部分并不容易证明，我们考虑进行如下转换。

如图所示，h_j (V_p - V_q) 是在 h_i(V_i - V_k) 的上多边形的最优划分中离 h_i 最近的水平弧，同理定义 h_k 是 h_j 上方最近的水平弧。由于 h_j 显然应当是正贡献的，那么

根据前面提到的性质，我们知道 S(h_k/h_i) \geq S(h_j/h_i)，也就是“天花板越低，支持系数越低”。将这个性质拓展后，我们就能得到最开始希望得到的性质：

那么 (1) 蕴含了 (2)，我们就证明了这个定理。

在这个定理下，我们可以提出一个增量的算法思路。我们在把所有的潜在的水平弧找到后，从上往下进行枚举，并不断算出其上多边形的最小最优划分。在地板不断往下移动的时候，根据前面对支持系数的定义，当前已经确认的潜在水平弧将有可能失效（但不可能重新出现），我们只需要快速完成判断即可。

接下来，为了可以让失效的行为变得更有规律性，我们来为这个算法进行更多的理论补充。

我们首先定义一个潜在水平弧的上限弧。我们从高到低对上限弧进行构造。为统一记号，称 h_i 的上限弧为 U_i。

• 首先，令 h_n 的上限弧为 h_n。
• 其次，从高到低考察剩余的潜在上限弧。假设目前考虑的是 h_i，那么它的上限弧是最低的 h_k，满足 S(h_k/h_i) > S(U_k/h_k)

然后我们定义潜在水平弧之间的父子关系。我们称 h_j 是 h_i 的一个子弧，当切仅当

我们可以注意到一个事实：h_i 的所有子孙都会在 U_i 和 h_i 约束出的多边形中，并且在最小最优化分中，处在这个多边形内的所有水平弧都是 h_i 的子孙。

另外一个可以注意到的事实是，如果 h_j 是 h_i 的儿子，那么我们有 U_j 不高于 U_i，故 U_i - h_i 多边形之间只会有包含或者并列的关系。

我们可以证明两个重要定理。

定理 2.2：一条潜在水平弧出现在最小最优划分中可以推出其上限弧也出现在最小最优化分中。

证明：待补充。

定理 2.3：一条潜在水平弧出现在最小最优划分中当且仅当其父弧也出现在最小最优化分中。

证明：待补充。

推论 2.1：一个“祖先弧”和它的所有后代必然在最小最优化分中同时出现或者同时不出现。

证明在此略去。

于此同时，利用支持系数的定义，我们可以导出如下定理：

定理 2.4：对于 h_i, h_j（h_j 在上方），假设被二者约束的多边形的最优划分是一个扇形，那么如果 S(U_j / h_j) \geq w_i，那么 h_j 不会在以 h_n 为上边沿，低于或等于 h_i 的任何潜在水平弧为下边沿约束得来的多边形中起正贡献。

证明：利用反证法可以轻松得到，在此略去。

根据定理 2.3，我们可以从潜在水平弧的“族谱”中的叶子节点作为起点，并一步步向上扩展。当我们在考察 h_i 的时候，根据推论 2.3，我们实际上完全可以将 h_i 已知的所有儿子和它作为同一个单元——或者说，所有儿子被压缩到这一条弧上。我们假设紧靠在 h_i 下方的潜在水平弧为 h_b，那么只需要考察 w_b 和 S(U_i/h_i) 的大小关系，就可以知道 h_i 在被 U_i 和 h_b 约束的多边形中是否起正贡献。如果其起到负贡献，那么根据定理 2.4，我们可以自信的把 h_i（连同它的所有子孙）全都删除。

而需要注意的是，根据父子关系的定义，我们可以在从高到低的扫描过程中逐步完善整个父子结构——当我们搜索到一条弧的时候，其上方所有弧的父子关系都会被明确，并且弧自身已经被恰当的压缩或者删除。

我们终于可以给出解决单调基础多边形的最小最优划分的 O(n) 算法。

1. 通过前面提到的单次扫描算法，得到所有的潜在水平弧。我们将其从高到低进行排布（而在实际的计算过程中，它们已经被这样排布了）。
2. 从高到低枚举所有未被退化的潜在水平弧。令 h_j 为当前处理的潜在水平弧，而 h_k 与 h_i 分别为仅靠在 h_j 上/下方的潜在水平弧。我们此时保证 h_j 的上多边形中的最小最优方案已经被动态维护。我们同时获取了未被删除的所有潜在水平弧对应的上限弧。 我们首先确定 h_j 的上限弧和子弧。我们不断将 S(h_k/h_j) 和 S(U_k/h_k) 进行比较。
   • 如果前者不大于后者，那么其满足子弧的性质，我们就可以清晰的知道 h_k 是 h_j 的子弧。我们将 h_k 和其所有子孙合并到 h_j 下，并借助支持系数的性质直接得到 S(U_k/h_j)。此时，U_k 成为 h_j 对应的新的 h_k。我们进行替换后回到 2. 最后的循环。
   • 反之，h_k 就是 h_j 的上限弧，我们进入下一步。
3. 接下来，我们考察 S(U_j/h_j) 和 w_i 的关系。
   • 如果前者不小于后者，那么 h_j 在今后必然起负贡献，我们直接将 h_j 和它的所有后代删除，并将 h_j 更新为 h_k，并同时更新 h_k 为 U_k。随后回到 3. 对应的循环。
   • 反之，h_j 目前可以起正贡献，我们直接进行下一步。
4. 此时，关于 h_j 的信息已经被全部处理完。我们只需要将 h_j 替换为 h_i，开启对下一个潜在水平弧的考察。

最后剩余的潜在水平弧直接对应了最小最优划分。其中，这些潜在水平弧将多边形分为若干部分，而每一部分都是扇形划分。我们据此即可直接构造出方案，并进行后续的计算。

这个算法的正确行证明在此省略，而线性复杂度是显然的。

Chpt. 4 普通多边形

我们将上述算法从单调多边形的特例迁移到普通的情况。我们依然固定下全局最小值，那么此时将会存在若干个局部最大值，而由于潜在水平弧并不会交叉，我们可以发现它们形成了一个树状结构（需要注意的是，这个结构只依赖于它们的端点形成的区间对应的包含关系，而不等同于前面提到的父子关系）。我们在这个树状结构上定义一个弧的子树，其和普通树形结构同理。我们也能定义潜在水平弧的上下关系，并且这个上下关系实际上和这个树状结构同步。我们在此省略形式化证明过程。

在这个情况中，一个水平弧对应的下边沿弧实际上还是单一的，而由于其树状结构的特性，其可能包含很多个上限弧，限制住了弧的子树。支持系数的参数也因此产生变化。

定义 S(\{h_j, h_k, \cdots\}/h_i) 表示上边沿为 h_j, h_k, ... 首尾通过多边形的侧边连接形成的大上限弧中，h_i 对应的支持系数。公式依然是不变的，支持系数满足的分子分母分别相加的性质也能类似沿用。

在上面给出的图中，S(\{h_5, h_7\}, h_2) 式子中对应的大上限弧就是 V_7 - V_{10} - V_6 - V_9 - V_8。

我们重新规范一下上限弧的定义，因为此时的上限弧形成了一个集合。

• 对叶子节点，其上限弧只有本身。
• 否则，对一个水平弧 h_i，其上限弧 h_k 需要满足：
  • 上限弧之间不存在包含关系，而只能并列；
  • 没有在 h_k 之下且在 h_i 之上的弧同时满足上述性质。

不过，由于在一条弧下方的所有弧依然是线性排列的，子弧的定义依然适用。

原文中忽略了接下来讨论的细节，并直接指出：支撑算法 1 正确性的定理 2.2，定理 2.3，推论 2.1 和定理 2.4 在普通多边形上依然适用，而区别仅在于将诸如“h_i 是 h_j 的上限弧”的描述改为“h_i 在 h_j 的上限弧集合中”。也就是说，这个上限弧集合是互相紧密联系的。

接下来，我们照着算法 1 的思路，给出最终的算法，其成功的在 O(n \log n) 的复杂度下解决了原问题。

1. 通过前面提到的单次扫描算法，得到所有的潜在水平弧。我们在得到的序列上线性构造出弧的树形结构（过程中只需要维护树的一条当前弧即可，参考笛卡尔树的构造流程）。我们顺便将局部最大值插入到树中作为儿子，并视为被退化的潜在水平弧。
2. 从儿子到根枚举（或者说后序遍历）所有未被退化的潜在水平弧。令 h_j 为当前处理的潜在水平弧，而 X 与 h_i 分别为仅靠在 h_j 上/下方的潜在水平弧（集合）。我们此时保证 h_j 的上多边形中的最小最优方案已经被动态维护。我们同时获取了未被删除的所有潜在水平弧对应的上限弧。我们考察 \max_{h_x \in X}S(U_x/h_x) 和 w_j 的关系。
   • 如果前者不小于后者，令 h_k = \argmax_{h_x \in X} S(U_x/h_x)，那么 h_k 在今后必然起负贡献，我们直接将 h_k 和它的所有后代删除。同时，我们在 X 中删除 h_k 并添加 h_k 的所有上限弧。然后，我们回到 2. 对应的循环。
   • 反之，X 的所有弧目前可以起正贡献，我们直接进行下一步。
3. 然后，我们确定 h_j 的上限弧。我们不断将 S(U_j/h_j) 和 \max_{h_x \in X}S(U_x/h_x) 进行比较。
   • 如果前者不大于后者，令 h_k = \argmax_{h_x \in X} S(U_x/h_x)，那么其满足子弧的性质，我们就可以清晰的知道 h_k 是 h_j 的子弧。我们将 h_k 和其所有子孙合并到 h_j 下，然后在 X 中删去 h_k 并加入其所有上限弧。随后，我们借助支持系数的性质直接得到 S(X/h_j)。我们即可回到 2. 最后的循环。
   • 反之，X 就是 h_j 的上限弧集合，我们进入下一步。
4. 此时，关于 h_j 的信息已经被全部处理完。我们只需要根据后序遍历的顺序继续下去即可。

注意到我们交换了两个操作的顺序。这是因为在一开始就把当前考虑的水平弧删除后，需要对其上限弧逐一考虑，有可能会导致复杂度退化。在交换前后顺序并改写判定负贡献的形式后，我们就能保证复杂度。

注意到这个算法的瓶颈是时刻维护一个集合的 \argmax_{h_x \in X} S(U_x/h_x)，并支持删除对应的最大元素。与此同时，我们还需要合并两个这样的数据结构（由于只有至多 n-3 条弧，那么合并的总时间复杂度可以视为将 O(n) 个只包含单个元素的堆以任意顺序合并的复杂度）。我们可以使用任何一个支持该操作的单 \log 数据结构完成这一点，例如在平衡树上实现 Finger Search，或者直接使用左偏树合并（论文另版最后的示范代码就是利用左偏树保证了复杂度）。如果使用常用的堆模型并直接进行启发式合并，那么对应的时间复杂度为 O(n \log^2 n)。关于 Finger Search 相关知识，请参考这里。

另外一个可以注意到的点是，考虑到上限弧在支持系数上的偏序关系，我们把 X 的定义转化为在当前弧上方的所有水平弧也是正确的。你可以灵活改变这个定义，从而优化代码的常数。

至此，我们终于可以在 O(n \log n) 的时间复杂度内解决整个问题。以上就是整篇论文的全部内容。