计算几何入门 7:凸包的构造——分治法

时间:2024-05-23 12:47:17

Graham Scan算法说明了凸包构造问题的下界O(nlogn)是可以达到的。其实O(nlogn)的算法远不止这一种,分治法就是一种能达到O(nlogn)复杂度的思想。在此引入运用分治思想的两种算法来构造凸包。


一、归并排序与分治思想

引入新算法之前依旧先来回顾一个经典排序算法:归并排序(merge sort)。归并排序的基本流程如下:

计算几何入门 7:凸包的构造——分治法

算法分为两个阶段:分(divide)和归并(merge)。分的阶段将待排序列均分到一个个子序列(如图中划分到单个元素)。归并阶段将分好的子序列两两合并成有序序列,重复合并的过程直到整体归为一个序列。归并过程共logn步,每步耗费n的时间,总体复杂度为O(nlogn)。


归并排序的过程就是一个典型的分治(divide-and-conquer)策略。凸包构造问题也可以套用这种策略来分而治之,逐步求解。我们可以将待处理点集S分为同等规模的两个子点集,并分别对其求凸包。

计算几何入门 7:凸包的构造——分治法

有了两个子解后,问题就变成了如何适当加一些边,将两个子凸包merge成整体解。分治法核心的任务就是如何merge。


二、分治法(1)

接下来的分析不考虑退化情况,比如三点共线等特殊情况的处理。

分治法解决问题的过程可以概括为:大事化小,小事化了。就是首先将问题划分为易求解的子问题,子问题套用已知方法解答即可。例如子凸包的构造就能用Graham Scan来解决。


Graham Scan解决问题的前提是:参照基准点,其他点按极角有序排列,也就是构成了一个有序的星形多边形(star-shaped polygon)。首先要做的就是将两个子凸包预处理成两个star-shaped polygon。


由于任何一个凸多边形都是star-shaped polygon,它必然有一个,其他点按极角有序排列。问题在于如何找到一个公共核,使得两个子凸包同时关于这个核是极角有序排列的。也就是公共核处于两个凸包的交部分,这样是最好处理的情况(如下左图)。不过还有可能有其他情况,不能找到公共核(如下中图),甚至两个凸包根本不相交(如下右图):

计算几何入门 7:凸包的构造——分治法计算几何入门 7:凸包的构造——分治法计算几何入门 7:凸包的构造——分治法

这就要将分治策略分不同情况来实现。首先看最简单的情况,两个子凸包有公共核。


先找其中一个子凸包的核,我们可以任取该子凸包上的三点构成三角形,求三角形重心作为核。然后判断这个核是否也在另一个子凸包内部,若判定为真,就是有公共核的最简单情况。判定方法也就是之前提过的in convex polygon test,对凸包每条边做to left test即可,在线性时间内可以判定。

计算几何入门 7:凸包的构造——分治法

相对于公共核,两个子凸包的各自有序排列,相互交错。要做的就是将二者点序列合并,方法正是典型的二路归并,线性时间可以完成。最后进行Graham Scan即可得到大凸包。


存在公共核的情况处理是很简单的,再看第一个子凸包的核落在第二个子凸包外部的情况。如下图所示:

计算几何入门 7:凸包的构造——分治法

这中情况与增量构造法的情况很相似,P1的核x相对于P2就是一个新加入的点。做出两条support line:x→t和x→s,舍弃P2上t→s路径的点即可。这样P2中剩余点与x构成了一个星形多边形,x也成为了P2的核。这就转化成了第一种有公共核的情况。


三、分治法(2)

上述分治策略的算法过于复杂,所以引入一种更加简明的分治策略。这种分治策略也会为三角剖分等问题提供思路。

首先规定一种点集划分的策略。假设待合并的两个子凸包是沿着某方向是分离的,二者不想交。例如下图凸包P1和P2就是相互分离的:
计算几何入门 7:凸包的构造——分治法
这样划分会使得合并更加简明,不必区分多种复杂情况。为了满足这种划分策略,引入一种预处理,也就是一个x方向的排序过程(X-sorting)。排序后就可取点x坐标的中值,将点集划分为规模相当的左右两个子集。每个凸包都有其最左点l最右点r,如上图。

merge操作就是将两个左右相离的两个子凸包合并为一个大凸包的过程了。运算的关注的正是两对l和r点。

先直观感受一下merge操作要添加的新极边:
计算几何入门 7:凸包的构造——分治法
上下两条紫色边正是要求的新边,又称支撑边(support line),并且每次merge只会增加两条新边。两条边类似两个圆的公切线(common tangent),将二者连接起来。

直观上感觉,两条support line正是两个子凸包的最高点t和最低点b相互连接得到的,这些点只需线性时间就能找到。当真如此的话凸包构造的下界就成了O(n),显然直觉是错误的。例如下面的两种情况,support line就和b、t两点没有直接关系了:
计算几何入门 7:凸包的构造——分治法      计算几何入门 7:凸包的构造——分治法
构造support line的过程需要缜密的分析,并非凭直觉能得到的。

构造过程首先从左凸包的r点右凸包的l点连线开始,以这条线为基础逐步得到support line。
计算几何入门 7:凸包的构造——分治法
注意一个细节问题:如何得到各子凸包的l点和r点。每次合并都会产生新的凸包,所以凸包是一个动态的结构。当然可以每次计算出最左点和最右点,只需要线性时间。但是这并不是最优的方式。考虑分治的思想,就整个merge流程来讲,是自底向上将子凸包两两合并的过程。因此只要在最底层上最小的子凸包中记录最左点和最右点,每次merge更新一下这两个变量即可,只需要O(1)的常数时间!这种优化对整体的复杂度上线nlogn虽然没有影响,也能为程序节省一部分的开销。

再看如何将最初的r-l线变成support line,在此以upper support line为例。算法的核心依然是to left test。

观察support line的两个端点的特征,可以看出他们对于前驱后继都是RR或LL型的,也就是前后相邻的点都落在support line的同侧。其余任两点的连线都只能是LR或RL的,这也是增量构造算法的核心思想。两次to left 测试即可得出类型。

从r-l线出发,首先看l点,可以发现其前驱后继相对于r→l是RL型的。若要得到RR型的特征,必须向其后继方向推进一个单位。
计算几何入门 7:凸包的构造——分治法
将l点向其后继推进一单位,更新了r-l线。判定l点依旧是RL型的,r-l线还不是support line,继续推进l点。判定新的r-l线,l点的特征变为了RR型,暂时可以认为l点满足要求,接下来考察r点。

r点的前驱后继对于线l→r是RL型的,若要得到LL的特征,必须向其前驱方向推进一个单位。以此往复,直到r点特征变为LL。

然后回头考察l点,发现此时l点已经不满足RR了,变回了RL。继续同样的步骤推进l点直到特征变为RR。然后在回头考察r点,发现它依旧满足LL,算法停止。至此r和l两点连线就是upper support line了,同样lower support line构造方式类似。

回顾由r-l线逐步推进得到support line的过程,每次操作一个端点,得到是一种“Z”字形(zig-zag)的推进轨迹。操作点的切换由另一点满足要求决定,而算法停止的依据是两个端点同时满足了要求。这种方式类似快速排序构造轴点的过程,左右两轴点交替操作,直到二者都满足要求时算法停止。

如此通过两次“zig-zag”的过程就能得到两条support line,完成两个子凸包的合并。

分析一下算法时间复杂度。算法首先要按照x坐标排序,排序复杂度为O(nlogn)。再看merge过程,无论是左侧子凸包还是右侧子凸包,对于其每个点的操作至多只有以此,也就是每次归并是线性时间。归并共logn次,算法的总体复杂度就是O(nlogn)了。

最后总结一下第二种分治法的特点。此前Jarvis March算法虽然以平方复杂度为上界,但其”输出敏感性“使得实际复杂度为O(hn),最好情况下仅甚至为线性。例如如下情况:
计算几何入门 7:凸包的构造——分治法
Jarvis March算法的复杂度变为了O(4n),而此种分治法依旧会经历按部就班的X-sorting,一上来就注定了O(nlogn)的复杂度,然后经历同样O(nlogn)的merge过程。也就是说这种分治法在各种情况下的表现都是很均匀的。

本文是学堂在线课程《计算几何》的笔记,帮助理解和记录思考过程,不够严谨请见谅。