在上一篇笔记中,我们介绍了构造凸包的几种算法。但是很可惜的是,这些算法都很难让我们感到满意。最主要的原因就是其时间复杂度太高。本篇笔记,我们将介绍拥有最优时间复杂度的Graham Scan凸包构造算法。

Lower bound of CH construction

这里我们介绍一种很重要的证明算法复杂度下界的方法:Reduction。使用Reduction的动机在于:我们对于一些研究不那么透彻的问题,往往无法直接从证明给出它的时间复杂度。通过 Reduction 我们就能通过一些已知时间复杂度的算法,去得到未知问题的时间复杂度的下界(lower bound)。

这里我们介绍的 Reduction 是规约的一种特例,线性规约。线性规约要求我们输入与输出之间的转换一定是在 $O(n)$ 内完成。

Reduction 基于这样的一个想法:如果我们能够把 已知问题A的输入转换成 未知问题B的输入,把 未知问题B的输出转换成 已知问题A的输出,那么就可以说我们解决未知问题B,就是在解决已知问题A。我们根据其他的知识,往往可以得到已知问题的复杂度的下界,自然无论 未知问题B 采用何种算法,其复杂度都不能低于这个下界,否则我们就构造出了 问题A的一种复杂度低于lower bound的算法。这显然是不可能的。

这个流程,我们称作 Problem A is reducible to problem B.

在这里,我们借助排序问题(基于代数判定树)来对凸包构造问题进行规约分析。
我们知道,基于 algebra decision tree的排序算法,其时间复杂度的lower bound一定是 $\Omega(nlogn)$ 的。
我们只要能找到可以在 $O(n)$ 的限定下完成 input / output 之间的转换就可以完成这个规约的过程。

下面来介绍一下我们具体的规约过程:

Input 考虑在实数轴上的一系列点,按照某个抛物线方程($y=x^2$)进行二维映射 $(x) -> (x,x^2)$。我们将所有映射得到的点,纳入点集 $P$。这个过程花费 $O(n)$ 的时间。

构造凸包 我们在点集 $P$上构造一个凸包。

output 我们按照 ccw 的顺序,从 LTL 开始遍历所有的极点。最终得到的输出的序列就是对这列实数排序的结果。这个过程也花费 $O(n)$ 的时间。

到此为止,我们的 Reduction 就完成了。因为我们知道,基于 ADT 的排序算法,其时间复杂度的 lower bound 一定是 $O(nlogn)$,所以凸包构造算法的时间复杂度的 lower bound 一定不小于 $O(nlogn)$ 。

下面我们要介绍的三种凸包构造算法,其时间复杂度就是 $O(nlogn)$ 的。

Graham Scan

我们直接介绍 Graham Scan算法的流程。

Code of Graham Scan

1
2
3
4
5
6
7
8
9
10
选择leftest-and-lowest的点作为p0
选取所有的 pi 属于 P\{p0} 构造得到 (p0,pi)
按照极角排序 得到排序后的点集 P
构造栈 S、T
S[0] = P[0]
S[1] = P[1]
循环 当 T非空:
toLeft(S[1],S[0],T[0])?
S.push(T.pop()):
S.pop();

现在我们从更形象化的角度去理解 Graham Scan
我们现在已经有了初始的一条极边 **(1,2)**,并且对所有的点进行了排序。假设已经行进到了第九个点。

此时,第十个点位于蓝色区域(ToLeftTest(1,9,10):Right)。此时,我们对其前驱的若干节点进行回溯(S.pop())。回溯直到第五个点发现此时,ToLeftTest(1,5,10):Left。此时将10推入S,并且使得10从T中推出(S.push(T.pop()))。

如果落在绿色区域(ToLeftTest:Left)呢?此时直接使得:**S.push(T.pop())**即可。

现在,我们需要考虑的是如何按照极角排序,这里给出一段C++代码:

1
2
3
4
5
6
7
bool polarOrder(Point a,Point b){
int order = ccw(pivot,a,b);
if(order == 0)
return sqrtDist(pivot,a) < sqrtDist(pivot,b);
return order == -1;
}
sort(points + 1,points + N,polarOrder);

这里的 sort 函数是由 algorithm 头文件提供的。当然,我们还有其他的算法去进行极角排序,这里就不深究这个问题了。

Cost of Graham Scan

我们在本节笔记的开头计算了凸包构造算法的lower bound。那么, Graham Scan是否就是最优的算法呢?

我们从算法的流程来看看它花费的时间:

1
2
3
选取LTL // O(n)
极角排序 // O(n)
循环 出入栈 // O(?)

我们看到,需要分析的关键就在于最终的循环。
我们的确有所顾忌:一次一次的出入栈是否会使得复杂度不仅仅是线性的。

我们可以至少通过两种方法来介绍这个循环的复杂度仅仅是 $O(n)$ 的,这里仅介绍图论的方法。

图论的方法 我们考虑所有的出入栈过程中构成的边,如图中的(1,2)(2,3)(3,4)(5,2) … 我们能够证明的是,所有的这些边能够构成的图一定是一张平面图,也就是边与边之间并不会存在交点。因为所有的新的边,智慧出现在蓝色或者绿色区域,以及回溯得到的边也只会出现在原凸包的外部,因此构造出来的图一定是平面图。

根据欧拉公式,n个节点构成的平面图,其上边的个数一定是O(n)的。

至此,我们已经构造性地证明了凸包构造算法的确有时间复杂度为 $O(nlogn)$ 的算法,Graham Scan算法。Graham Scan也是在最坏时间复杂度的意义上有最好性能的算法。