凸壳算法时间复杂度的深化改进研究

5.2.2　凸壳算法时间复杂度的深化改进研究

笔者的研究表明：由周启海教授提出的凸壳算法时间复杂度基本定理，不仅是完全必要的、十分正确的；而且澄清了国内外凸壳算法研究学术界的若干误识。

凸壳算法时间复杂度基本定理　记二维点集S={P（_ix_i，y_i）│1≤i≤m，3≤m＜∞}由给定平面内的点构成，Q是S的凸壳，Q_i∈S是凸壳Q的各顶点（i=1，2，…，n），S_Q={Q_i│Q_i∈S，i=1，2，…，n}是凸壳Q的顶点集。假设“找出二维点集S的凸壳Q各顶点所构成的凸壳Q顶点集S_Q”的生成凸壳顶点子算法1的时间复杂度为T₁（m），而“使凸壳Q顶点集S_Q中各顶点，按照凸壳Q各顶点自然顺序的有序化排序”的凸壳顶点排序子算法2的时间复杂度为T₂（n）；那么，求解凸壳问题的凸壳算法时间复杂度T（m）=T₁（m）+T₂（n）。

证明：首先，生成凸壳顶点子算法1的处理结果数据集（即Q_i∈S是凸壳Q的各顶点，i=1，2，…，n），显然必定为凸壳顶点排序子算法2处理的输入数据集。

其次，生成凸壳顶点子算法1的处理，总不依赖凸壳顶点排序子算法2的处理及其处理结果，故生成凸壳顶点子算法1的时间复杂度T₁（m）必与凸壳顶点排序子算法2的时间复杂度T₂（n）无关。反之，凸壳顶点排序子算法2的处理，则必定依赖生成凸壳顶点子算法1的处理及其处理结果，故凸壳顶点排序子算法2的时间复杂度T₂（n）与生成凸壳顶点子算法1的时间复杂度T₁（m）有关；例如一种可能出现的极端情形是：如果生成凸壳顶点子算法1所得处理结果，恰好就是二维点集S的凸壳Q的有序化各顶点，则无需对凸壳Q的各顶点进行凸壳顶点排序子算法2的有序化处理，故凸壳顶点排序子算法2的时间复杂度T₂（n）此时可为零，即凸壳顶点排序子算法2的时间复杂度T₂（n）的下界可能为O（1）。

因此，无论何种情况下，求解凸壳问题的凸壳算法时间复杂度必有：T（m）=T₁（m）+T₂（n）。证毕。

图5.2　凸壳的顶点集与内点集结构示意图

定理5.1　若二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜∞}由给定平面内的点构成，Q是S的凸壳，Q_i∈S是凸壳Q的各顶点（i=1，2，…，n），S_Q={Q_i│Q_i∈S，i=1，2，…，k，k+1，k+2，…，n−2，n−1，n}是凸壳Q的顶点集；则“使凸壳Q顶点集S_Q中各顶点，按照凸壳Q各顶点自然顺序的有序化排序”，等价于对凸壳顶点的升序（或降序）排序处理。

证明：不失一般性，可设如图5.2所示，已知二维点集S={P_i（x_i，y_i）│1≤i≤m，3≤m＜∞}的凸壳为Q，凸壳Q的顶点集为S_Q={Q_i│Q_i∈S，i=1，2，…，k，k+1，k+2，…，n−2，n−1，n}；顶点Q₁（x₁，y₁）、Q_k（x_k，y_k）分别为凸壳Q的最左顶点、最右顶点，称线段Q₁Q_k为凸壳Q的横向直径；称横向直径Q₁Q_k所划分出的多边形Q₁Q₂Q₃…Q_k−2Q_k−1Q_k为凸壳Q的下子凸壳Q_下，称横向直径Q₁Q_k所划分出的多边形Q₁Q_kQ_k+1 Q_k+2…Q_n−2Q_n−1Q_n为凸壳Q的上子凸壳Q_上。

（1）把凸壳Q的上子凸壳Q_上（含其各顶点、内点），整体平移映射对接到凸壳Q的下子凸壳Q_下的上方，且使上子凸壳Q_上的最左顶点Q₁平移到下子凸壳Q_下的最右顶点Q_k处，如图5.3所示。

图5.3　凸壳的上凸壳平移对接到下子凸壳的右上方示意图

平移对接后，可施行如下一一映射：

若记d_x=x_k−x₁，d_y=y_k−y₁；则平移映射上凸壳Q′_上的亚顶点Q′_i（x′_i，y′_i）与原上凸壳Q_上的顶点Q_i（x_i，y_i）的X坐标值之间，必满足一一映射的亚顶点平移关系式

（2）把凸壳Q的平移映射上凸壳Q′ _上（含其各顶点、内点），以x= x_k为对称轴，镜像映射对称到凸壳Q的下子凸壳Q_下的右侧方，且使平移映射上凸壳Q′的最右顶点Q′_k映射为下子凸壳Q_下的最左顶点Q_k处，而平移映射上凸壳Q′的最左顶点Q′₁映射为下子凸壳Q_下的最左顶点Q₁的镜像点处，如图5.4所示。

图5.4　凸壳的上凸壳镜像对称到下子凸壳的右侧方示意图

若记D=x₁+x′_k+d_x=x₁+（x_i+d_x）+d_x=x₁+x_k+2d_x；则镜像映射准顶点Q″_i（x″_i，y″_i）必满足一一映射的准顶点镜像（以x= x_k为对称轴）关系式

x″_i = D−x′_i　=（x₁+x_k+2d_x）−（x_i+d_x）=x₁+x_k+d_x−x_i

y″_i = y′_i−d_y =（y_i+d_y）−d_y = y_i

显然，对各准顶点Q″_i（x″_i，y″_i）按其x坐标x″_i的升序（或降序）排序处理所得结果——“有序化准顶点序列”，必同构于凸壳Q各顶点的X坐标x_i自然顺序有序化结果。

（3）再经逆变换x_i = x₁+x_k+d_x−x″_i处理后，就可把“有序化准顶点序列中各准顶点Q″_i（x″_i，y″_i）（注意：实际上，它已为Q″_i（x″_i，y_i）），还原为已按照凸壳Q顶点自然顺序有序化的各原顶点Q_i（x_i，y_i）——“有序化凸壳顶点序列”。这表明：对凸壳Q各顶点自然顺序的有序化排序，必等价于对各准顶点Q″_i（x″_i，y″_i）的X坐标值x″_i的升序（或降序）排序处理。

因此，定理5.1成立。证毕。

依据此凸壳算法时间复杂度基本定理和定理5.1，可有如下重要推论。

推论5.1（内点全无推论） 在凸壳算法时间复杂度基本定理中，如果二维点集S均由凸壳Q各顶点构成，即m=n；则求解此时的凸壳问题，其凸壳算法时间复杂度必为T（n）=T₁（n）+ T₂（n），其下界为T₁（n）+O（n log n）。

证明：即使二维点集S均由凸壳Q各顶点构成，但一般说来，对于S中各点究竟是否为凸壳Q的顶点，显然只有经生成凸壳顶点子算法1处理完后，方能最后确定。此时，生成凸壳顶点子算法1的时间复杂度为T₁（n），通常是不可忽略的。凸壳顶点排序子算法2的时间复杂度为T₂（n），而T₂（n）的一般情况时的下界为排序算法的已知下界 O（n log n）。因此，求解此时的凸壳问题，其凸壳算法时间复杂度下界必为T（n）=T₁（n）+T₂（n），其下界为T₁（n）+O（n log n）。证毕。

应当指出，推论5.1已清楚地表明：

（1）因为生成凸壳顶点子算法1的时间复杂度T₁（n），独立于凸壳顶点排序子算法2的时间复杂度T₂（n），且通常是不可忽略的；所以，国内外凸壳算法研究学术界迄今为止所公认的凸壳算法时间复杂度下界为“T（n）=O（n log n）”，原来只不过是对“T（n）= T₁（n）+O（n log n）”的一种误解，或者充其量只能算是对“T（n）= T₁（n）+O（n log n）”的一种大误差的近似。

（2）凸壳算法效率的有效提高（甚至大幅提高），不仅可能，而且必能（顺便指出：这正是周启海教授率领其创新研究团队，坚定不移地致力于凸壳算法同构化创新的理论基础与成功保障）。

推论5.2（内点过重推论） 在凸壳算法时间复杂度基本定理和定理5.1中，如果二维点集S中，其凸壳Q的内点远多于顶点，即m＆gt;＆gt;n，且两者子算法之时间复杂度T₁（m）＆gt;＆gt;T₂（n）；则求解此时的凸壳问题，其算法时间复杂度下界必不取决于T₂（n）=O（n log n），而主要取决于T₁（m）。

此推论5.2的正确性是无容置疑和显而易见，故毋需赘述其证明。