凸包问题的优化算法

在上一篇笔记中,我们介绍了构造凸包的几种算法。但是很可惜的是,这些算法都很难让我们感到满意。最主要的原因就是其时间复杂度太高。本篇笔记,我们将介绍拥有最优时间复杂度的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也是在最坏时间复杂度的意义上有最好性能的算法。

我所推荐的计算机在线课程与书籍 凸包问题

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×