Fl0w3r

carpe diem

Convex Hull

Posted on In
11k 20 mins.

引言

本节我们将探索计算几何的核心问题：凸包问题。计算几何领域几乎所有的问题都可以“归约”为凸包问题，因此学习凸包问题对整个计算几何体系至关重要。

Convexity

Why Convex Hull

我们计算几何的第一站就是凸包问题，它在计算几何中处于核心位置，这个核心体现在几乎所有的问题从理论上讲都可以归结为凸包问题。

Nails In The Table

接下来我们通过一个具体的动手实验领会一下凸包到底是什么。

为此你需要找到一张桌子或是屏幕，假想在这个桌子上钉上一系列的钉子，然后用皮筋将其撑到足够大以至于它能将桌面上的所有钉子都包含进去。

接下来的事情非常的轻松，你只要松手就行。那么随着啪的一声，你将会看到这幅图景：

刚才的皮筋就会变成这样一段一段蓝色的线段，它们首尾相连构成了一个紧绷的包围圈。这个蓝色的橡皮筋在在现在这样的一个图景状态就是我们所说的凸包，我们可以看到所谓的凸包是由这上面若干个钉子来决定的，虽然其中有一些钉子并不发挥作用，我们大致可以感觉到因为它们呆在内部。

那么，这之间的玄机又是什么呢？

Paint Blending

为了更好地理解什么是凸包，我们再来看一个应用的例子。

艺术家经常要通过混合得到某种他想要又不是从工厂直接生产出来的颜料。我们知道一般来说每种颜料都可以分成是红绿蓝三个分量的数值指标，每种组合对应的大致都是一种颜料。

我们不妨为了简便起见只考虑红的以及绿的两个分量，所以这样的话每一种颜料也就是它所对应的颜色都可以用红的和绿的这样两个数字，或者说它们在整体的成份中所占的百分比来对应。

C = (R, G)

比如说某种颜料 X 它所对应的红的分量可能是 10%，而绿的分量是 35%；另一种颜料比如叫 Y，那么它所对应的这两个分量一个是 16% 一个是 20%。 现在的问题来了，用这两种颜料能否兑出我们所希望的某些颜料呢？

X = (10%, 35%)  Y = (16%, 20%)

我们来看一下，当颜料混合在一块的时候它们的变化是多端的，有很多很多种组合，每几种颜料它们按照不同的分量、按照不同的比重勾兑在一块所得到的颜色其实都会不同。当然，艺术家有他的勾兑的方法，包括他的灵感，那么如果从数学的角度，从算法的角度来考虑，这其中应该用什么样的指导的方法呢？

那么从数学上来看我们一般来说都可以认为有一个目标的颜色，比如说这里的 U，这种颜色比如说特定的来说他希望红的占的比重是 12%，而绿的比重是 30%。

U = (12%, 30%)

对于这样的一种目标的颜料我们应该用刚才的 X、Y，这两种来自于工厂的原始颜料用什么样的比例来对它们进行混合和勾兑呢？

好，我想你已经知道这个答案了。没错 我们应该用两份的 X 和一份的 Y 勾兑起来，就可以得到 U 了。

你不妨去做个简单的验算，两份的 10% 再加上一份*的 16% 合在一块再除以 3，正好是 12%；而两份的 35%，再加上一份的 20% 也同样的除以 3 恰好也是 30%，所以用 2 比 1 的比例是这个问题的一个解。

好，如果说我们为此花费这些时间还是值得的话，我们还是希望得到一个方法，否则的话我们会很困惑，因为如果你没有掌握这背后的、统一的方法的话，那么如果下一次换一种颜色比如说这里的 V 它要求的是 13% 和 22%，那你可能又要花费一些时间了。

V = (13%, 22%)

那么首先一个问题是这种颜料能不能勾兑出来。并不是像我们这里所说的那样，每两种颜色给定了以后你都能勾兑出所有的颜色。其实在这个时候我们或许需要第三种颜色，比如这里我们也许从厂房里可以拿到第三种颜色 Z，它的对应的比重是 7% 和 15%。

Z = (07%, 15%)

好了，这个时候用这三种颜色是否能把它勾兑出来呢？

好，现在我来揭晓答案。正确的比例应该是一份的 X，三份的 Y 再加上刚才我们新添的第三种颜色 Z 一份 1 比 3 比 1。你可以按照刚才同样的方法去推算一下 验算一下，我想答案应该是它。

那么所有这里讨论的事情其实都是颜色，或者准确地讲是颜料之间的那种勾兑混合。这个东西和我们这里讨论的计算几何有什么关系呢？其实它们之间有着非常深刻的联系。

Color Space

既然谈到几何，那么少不了就要谈到它最最基础的一个概念叫做空间，欧氏空间。

在这里我们将欧氏空间对应于颜色，我们称之为颜色空间，具体来讲我们要将每一种颜色都对应成是这个空间中的一个点。无论这种颜色或者颜料是来自于生产厂家直接供应的那种基础性的颜料，还是艺术家为了创作的需要必须重新勾兑出来的新的颜色。总而言之每一种颜色都对应这个空间中的一个点。

当然这里因为我们讨论的都是正数，那可以认为它基本上都限于第一个象限，这不是主要的问题。那么现在的问题是在于我们固然可以按照这种方法将我们刚才的三种颜料也就是 X、Y、Z 按照横轴也就是刚才比如红色的分量数值以及纵轴，也就是刚才说的绿色的分量的数值对应地画出一个一个的点，三种颜料，分别是三种点。

我们刚才看到过，在我们只有 X 和 Y 两种颜料的时候如果我们要勾兑出 U，那个比重是 2 比 1。其实这件事情倒过来，我们在给出了固定的 X 和 Y 之后我可以将我们目标的那个 U 也在这个屏幕上画出来，如果你画出来的话你就会发现其实非常地巧，我们可以验证一下它们三者是所谓共线的。

如果是这种情况，那么我们认为 U 肯定是能被勾兑出来的，而且它的勾兑比例可以从几何上一目了然的能解释。

你可以再去计算一下，我会告诉你其实 U 到 X 的距离相对更短，U 到 Y 的距离相对更长，而二者的距离之比其实是 1 比 2，而我们刚才勾兑的比例是反过来的 2 比 1。

其实这就是一个规律，也就是说如果我要勾兑的一种颜色恰好是位于这两个顶点的那条连接的线段上，而且它们的距离存在一个比的话，那么这种颜色就必然能够被勾兑出来。而且勾兑的方法就蕴含在刚才的那个比例中，只要把刚才那个距离比 1 比 2 颠倒过来变成 2 比 1，它就必然能得到这种颜色。

你可以作为一个极端的例子去想一下，整个的是如果要勾兑 Y 和勾兑 X 本身的时候另一个分量是 0 是同样的道理。

好，那么刚才我们也可以解释为什么 V 这种颜色必须要借助第三种颜色才能够勾兑出来。因为你大致可以看出来因为 V 并没有位于 X 和 Y 所确定的这条线段上跑偏了，在这种情况下我们说必然要借助 Z，而之所以要借助 Z 或者说准确地讲按照我们刚才那个比例必须是 1 比 3 比 1 也蕴含在这个图中，原理是一样的。

如果在这种情况下我们要做的事情就是要首先确认 V 这个颜料所对应的那个点是不是落在 X、Y、Z 所定义的这个三角形的内部，如果是它就一定能勾兑出来；如果不是，至少它是不能勾兑出来的。

好，如果它能勾兑出来，具体的勾兑的比例是多少呢？在这个图中也给出来了，为此我们只需要去量一下 V 到这三个点的距离，然后找一下它们的比。我们在这里会发现它们的比恰好是 3 比 3 比 1，所以倒过来在这里我们勾兑的比例自然也就是这个最短的最近的这个点对应的那个颜色要取的更多，反其道而行之它要取三份；而到更远的那两个点所对应的颜色所取的比例要更少，完全可以用这个来度量

当然以上的这些结论你还需要在课后再做仔细的推导和严格的验证，在这里你不妨把这个结论记下来：也就是说如果有一种颜料能够被两种已知的颜料勾兑出来，它必然位于二者之间的那条连线上；如果是对于三种颜料的情况，那么某种目标的颜色能够被勾兑出来当且仅当在颜色空间中它位于这三个点所对应的那个三角形的内部，而勾兑的比例是与他们的距离成反比的。

Convex Hull

我们虽然不是很喜欢数学，但是不得不还要用一些简单的数学把刚才我们所看到的那个结论严格地表述出来。

也就是说我们如果给定的是平面二维空间中的一系列的点的话，那么这些点所对应的颜料能构造出哪些新的颜料出来呢？我们会发现其实每一种新的颜料从几何来讲，对应于原来那些颜料的某一个调和方案。

那么在这里有一些勾兑方案专门地称之为凸的勾兑方案，或者叫作凸组合 Convex Combination。具体而言，如果是一个凸组合需要有哪些条件呢？

我们说大致有两个主要的条件：

  1. 所有分量的总和必须是 100%
  2. 所有分量必须是非负的

Extreme Points

Extremity

在我们最开始给定的这些点中，哪些是最终对凸包有贡献的被皮筋绷住的，哪些是没有实质作用的，这种性质可以归纳为所谓的极性。

沿着刚才的那个思路，我们观察结论可以表述为这样的一幅图。我们看到在刚才的所有那些钉子中凡事被最终的皮筋绷住的钉子，暂时没有实质作用的这些钉子我们都用青色来表示，有什么本质不同呢？

if there exists a line L through p
    such that
        all points of S lie on the same side of L

数学上的观察告诉我们，所谓有用的点都有一个共同的特点：经过它们我们总能找到一条直线使得所有的点都落在这条直线的同一侧。

Strategy

在排序算法中有一个非常有意思的算法：起泡排序 Bubblesort。我们这里的算法设计和它是非常类似的：

如何甄别极点和非极点呢？

我们需要回忆颜料勾兑的例子，一种颜料能够被其他几种颜料勾兑出来当且仅当它落在某一个三角形的内部。反过来像极点这样不能被其他颜料勾兑出来的颜色它就不可能被包含于任何三角形的内部，这样的话我们又往前转化了一步，将我们的甄别任务转化为某一个点是否会被包含于另外的三个点所确定的三角形内部。

In-Triangle Test

根据刚才的分析，所谓凸包问题可以归结为一系列的判断：任何的一个点是否会落在其他的三个点所对应的三角形内部被它们包围，我们称这个为 In-Triangle Test。

基于 In-Triangle Test，我们就可以将非极点们一个一个地找出来并且将它们排除在我们的视野之外。

首先做初始化，要像无罪推论一样将所有的点都设定为极点。接着枚举出所有可能的三角形，对于每个三角形我们还要去考察除它们之外的每一个点 s；一旦我们发现 s 的确是落在当前这个三角形内部，我们就可以立即断定它不是一个极点，从而将它排除在外。

Make all points of S as EXTREME
For each triangle Δ(p, q, r)
    For each s in S\{p, q, r}
        If s in Δ(p, q, r)
            mark s as NON_EXTREME

void extremePoint(Point S[], int n) {
    for (int s = 0; s < n; s++)
        S[s].extreme = TRUE;

    // For each triangle
    for (int p = 0; p < n; p++) {
        for (int q = p + 1; q < n; q++) {
            for (int r = q + 1; r < n; r++) {
                // For each point
                for (int s = 0; s < n; s++) {
                    if (s == p || s == q || s == r || !S[s].extreme)
                        continue;
                        
                    if (InTriangle(S[p], S[q], S[r], S[s]))
                        S[s].extreme = FALSE;    
                }
            }
        }
    }

}

To-Left Test

我们给出的第一个基于极点的凸包算法虽然效率低下，但是它的意义还是很重要的，它会引出 To-Left Test，后面这个测试几乎是贯穿于我们计算几何这个课程的始终。

每当我们给定了一个点以及一个三角形后，如何来判定这个点是否落在这个三角形的内部？

依然是大事化小小事化了，我们将刚才这个 In-Triangle Test 转化为三次 To-Left Test。也就是说一个点如果确实落在某一个三角形的内部的话，那么相对于这个三角形的三条边所做的 To-Left Test 都会统一的返回 true。

所谓 To-Left Test，就是说这个点相对于有向线段而言位于左侧还是右侧。这里的敏锐观察可以归结为一个点如果落在三角形内部，它的充要条件当且仅当它相对于这三条直线的 To-Left Test 都是 true，它同时位于这三条直线的左侧。

那么现在问题转变为如何判断一个点在线段的左侧/右侧？

Determinant

bool ToLeft(Point p, Point q, Point s)
    return Area(p, q, s) > 0;

int Area2(Point p, Point q, Point s)    
    return p.x * q.y - p.y * q.x
         + q.x * s.y - q.y * s.x
         + s.x * p.y - s.y * p.x;

Extreme Edges

Definition

延续极点的思路推广到边，引入所谓的极边。

极边的候选者其实就是来自于任何两个相邻极点的连边，凡是对最终的凸包有贡献的那些边都称之为极边；凡是那些对凸包没有贡献的就不是极边，或者叫作非极边，non-extreme Edge。

就像我们定义极点一样，如果有一条这样的连边确实是极边的话，那么所有的点都会同时落在它的同侧，相应的另一侧就必然是空的。更具体来讲，以逆时针次序凸包边界每一条边都有这样一个特性：所有的点都恰好落在它的左侧，它们的右侧都是空的。

这样我们算法中的实质问题就自然地转化和具体化为如何来甄别任何两个点之间的那条连边是否为极边的问题。

Algorithm

Let EE = null
    For each directed segment pq
        If points in S\{p, q} lie to the same side of pq
            Let {pq} = EE

按照极边的思路，我们可以将伪代码细化为这样一段真实的代码：

void markEE(Point S[], int n) {
    for (int k = 0; k < n; k++) 
        S[k].extreme = FALSE;

    for (int p = 0; p < n; p++)
        for (int q = p + 1; q < n; q++) 
            checkEdge(S, n, p, q);
}

void checkEdge() {
    bool LEmpty = TRUE, REmpty = TRUE;
    for (int k = 0; k < n && (LEmpty || REmpty); k++) {
        if (k != p && k != q) {
            ToLeft(S[p], S[q], S[k])? LEmpty = FALSE: REmpty = FALSE;
        }
    }

    if (LEmpty || REmpty)
        S[p].extreme = S[q].extreme = TRUE;
}

Incremental Construction

Decrease and Conquer

接下来我们将从一个典型的算法思想减而治之 Decrease and Conquer 进一步改进。

一个经典的应该能回忆起来的算法就是插入排序 Insertionsort。插入排序整个思路可以归纳为将整个待排序序列存成线性结构，接下来在任何时候都将它分为排序和未排序两部分，在未排序部分随机找出一个（一般是两者分界的那个元素），通过一次查找在 sorted 子序列中找到这个元素对应的恰当插入位置。

同理，我们也可以应用于极边算法。

In-Convex-Polygon Test

递进式的核心技术是 In-Convex-Polygon Test，也就是判别多边形内部或者外部的问题。

我们要判断一个新引入的点是否是当前的极点，其实本质上就是判断当前这个点是否落在此前的凸包的外面或者是里面的位置关系。

要将刚才那种直觉转化成数学上的判断：每次我们递增式新引入的这个点如果是当前的 extreme point 的话，那么充要条件其实就是看它是否落在当前这个凸包的外面：如果落在外面那它就是下一个 extreme point；否则不是。

如果凸多边形确实是给定的，而且在此后要反复多次地做这类的查询的话，你是可以对这个多边形做一个预处理（本质上是排序）。

我们可以大致以一个点作为基础，在其余的 n - 1 个点中可以找到一个居中的连接起来确定一条有向线段。接下来又是我们刚才的惯用的 To-Left Test，经过这样一次常数成本的操作，我们确实可以判断出来这个未知的点到底是落在左边或者是右边，无论是哪边我们都可以将搜索的范围有效地收缩为原先的一半。

如此往复，我们每一次经过常数时间的成本都可以将这个问题的范围有效地降解为此前的一半，如此下去最终总会到达平凡的情况–trivial case：In-Triangle Test。

但是这个算法却不可行，最重要的是凸包并不是一成不变的，这种情况下我们的预处理是没有效力的。

与插入排序类似，sorted 部分本身就是动态的，即便可以使用二分查找，线性存储所带来的插入成本在最坏情况也会将这种优化无效化。

回到凸包，对于这种情况朴素的方法反而是最好的。我们可以沿着给定的凸多边形边界做习惯性的 CCW 逆时针旋转遍历，可以发现内部的点一定是在左手一侧的；反之如果我们在任何一段发现某一个点在右侧，那么可以立即断定它并非落在内部。

Support-Lines

其实我们还有一个任务要完成，解决如何将新引入的这个点附着或者是增加到原先的凸包上去，要使之成为一个完整的可以继续使用的结构。

凸包切线又被称为 Support Line。

Pattern Of Turns

只需要花费两次 To-Left Test，就可以明确确定一个顶点到底是来自 ts(L + R) 还是 st(R + L)。

Exterior/Interior

Jarvis March

Selectionsort

在介绍 GW 算法之前为了更好地理解它的算法思路，不妨温习一下之前我们很熟悉的选择排序。

与刚才的插入排序非常对称，在这里我们的 sorted 和 unsorted 部分是前后颠倒了，这个颠倒实际上是有本质区别的。

我们需要从 unsorted 部分中去找出一个最大的元素，接着将它进行一次交换挪到刚才 sorted 那个部分的首部。悄然之间，sorted 部分就向前迈进了一步。

那么这样一个算法思路从宏观的策略来讲我们可以概括为：每次我们都是维护一个局部的解，然后在尚未处理的部分中要去找到一个与当前的这个局部解紧密相关联的一个元素。没错，凸包就可以这么来做。

Strategy

我们如果反思一下在 Extreme Edge 那个算法中为什么会需要多达 n^3 的时间，就会发现根本的原因在于我们实际上考察的对象是遍布所有可能的那些边，这些边的总数会多达 n^2，每个又需要 n 时间鉴别。那么有什么改进的诀窍呢？

刚才的 selectionsort 就给了我们提示，也就是说我们或许能够将下一个的查找范围缩小到一个足够小的范围。

Jarvis 观察注意到一些结论：

  1. 所有构成凸包的那些边其实在拓扑上讲都是首尾相连构成一个环状结构的
  2. 如果构造过程确实是一条一条边构造，那么如果我在某一个时刻构造出一条边，那么接下来我必然可以沿着它的某一个端点向后继续去找到下一条 extreme edge

Coherence

该图可以说明如何在当前已有的这些极边基础上沿着下一个端点拓展出新的极边：

当前节点称作 k，它的前驱我们称之为 i，下一个极边则是 s。根据刚才 Jarvis 的判断，这个 s 必然来自于其他尚未处理的那些点中的一员。

而 s 之所以可以脱颖而出，其资本在于它是所有这些拐角中的最小者。也许有同学已经跃跃欲试准备用三角函数和反三角函数操作了，但其实有一种基本的技术就可以解决我们的问题。

To-Left Test

Lowest-Then-Leftmost

一个技术细节问题，也就是我们刚才说到的起点和第一条极边应该如何来找呢？

作为第一个点，它至少是极点。在这里针对于我们目前的算法需求，可以对问题进一步简化，也就是找到沿着 y 轴负方向最低的位置。这个点也就是所谓的 Lowest Point，在没有退化的情况下必然是 extreme point，所以我们可以以它为起点。

如果出现多个最低点的退化情况，则优先选择最左侧的点，也称为 Lowest-Then-Leftmost point。

Implementation

void Jarvis(Point S[], int n) {
    for (int k = 0; k < n; k++)
        S[k].extreme = FALSE

    int ltl = LTL(S, n);
    int k = ltl;

    // start with LTL
    do {
        P[k].extreme = TRUE;
        int s = -1;
        
        for (int t = 0; t < n; t++)
            if (t != k && t != s && (s == -1 || !ToLeft(P[k], P[s], P[t])))
                s = t;
        P[k].succ = s;
        k = s;
    } while(ltl != k)
}

初始化所有点都被视为非极点，接下来找到刚才所说的 Lowest-Then-Leftmost point 并且把它作为我们的第一个点 k 进入下面一个迭代循环。

每一个点当它进入这个循环的时候必为极点，第一个点如此，后面的点也一样。接下来我们则要找 s 是逐渐优化最终找到的极点，任何时候我们都未必知道它就是，需要遍历所有候选 t。

当 t 通过 To-Left 测试时什么都不处理，s 依然为候选者；反过来 To-Left 测试失败意味着出现在右侧，需要更迭 s 为 t。

int LTL(Point S[], int n) {
    int ltl = 0;
    for (int k = 1; k < n; k++)
        if (P[k].y < P[ltl].y || (P[k].y == P[ltl].y && P[k].x < P[ltl].x))
            ltl = k;
    return ltl;        
}

Output Sensitivity

Lower Bound

Reduction

在前面几节里我们围绕凸包的计算问题给了一系列的算法，从最开始的 n^4 极点算法一直到后面 n^3 极边的算法，再到 Jarvis march 以及 Incremental n^2，我们在沿着一条不断递减的路线在降低这个算法的复杂度。

但是如果计算模型是固定的话，必然有一个我们所说的 Low Bound 的概念：下界，也就是复杂度再低也不会低于某一个极限。

CAO Chong’s Methodology

三国中曹操的儿子曹冲有个很著名的故事：曹冲称象。

我们需要度量一个东西的难度，曹冲是要称出一头象的重量，他去找中间参照物石头，通过石头的重量估算出象的重量，而 Reduction 关系就是曹冲的船和水。

Transitivity

那么为什么这个问题可以像曹冲称象一样能够间接通过 A 问题的难度就得到 B 问题的难度呢？

对于 A 问题的任何一个输入，我们都可以曲径通幽式的先把它转化为 B 问题的输入，接下来调用 B 问题的任意算法得到输出，再转化为 A 的输出。

如果 A 问题确实存在某一个下界，而且这个下界是严格大于 n 的，那么我们说 B 问题的所有算法都不可能低于这个复杂度下界。

Reduction: Input

首先要把我们未知的那个问题（也就是那头象）摆在右边，这里我们考虑二维的凸包 2-dimensional convex hull 这个问题。

而石头则是 Sorting。也许初看这个问题可能会很迷茫，排序这个问题和凸包这个问题一个是纯粹的抽象计算问题，一个是具体的几何计算问题，二者之间怎么会有联系呢？

  1. 证明可以在线性时间内将排序问题的任何一个输入转化为凸包问题的输入
  2. 证明凸包问题的结果线性时间内转换回到排序问题

排序问题的输入可以理解为在数轴或者平面上 x 轴一系列的点，在图中我们只取了四个点。为了转换为凸包问题我们需要辅助线，以抛物线作为标尺将每一个点做提升变换，将 n 个数字转化为平面上的 n 个点。

Reduction: Output

来自抛物线上有线个点的凸包都具有这样的一个特性：最左侧的那个点和最右侧的那个点会在上面连上一条纵跨的一条单调直线。

这样我们就完成了 Reduction 的第二步：将凸包问题转化为排序问题。输入是无序的，输出是有序的，这正是排序算法的要求。

(注：这里有一个疑惑就是如果是正五边形，那么这个左右边界又该如何去界定呢？边界的连线并不单调。)

Sorting <=N 2d-CH

所以排序算法的下界是 nlogn，那么凸包问题也是如此，成为 Convex Hull 的下界。

Graham Scan: Algorithm

Preprocessing

那么我们来看一个下界意义上讲最优的算法：Graham Scan。

Graham Scan 首先要做的一件事情是一个预处理，一个排序。这个 presorting 其实就是要找到某一个特定的点，并且将其余所有的点按照这个点所对应的极坐标按极角来做一个排序。

那么具体的这样第一个点应该找谁呢？

其实任何一个极点理论上都是可以的，同样为了简化算法的解释和实现，我们不妨依然采用前面所讲过的 Lowest-then-Leftmost point 为 1 号点。

接下来会有与 1 号成角度最小的 2 号点，这里不妨假设 1、2 号点为同一高度，并且没有三点共线的情况，接着按照 (1, 2) 极轴的夹角从小到大命名其他点。

Graham Scan 算法的数据结构也很简单，只需要两个栈 T 和 S。初始化时依次将 1、2 入栈 S 中，其他 n-2 个点自顶到底存入 T 栈。

而排序可以选用任意排序，只是对象变成了点，而比较器变为 To-Left Test。

Scan

这个扫描过程中要关注三个东西：S 栈栈顶以及次栈顶、T 栈栈顶，我们可以用 S[0]、S[1]、T[0] 表示。

while(!T.empty()) {
    // test type of current turn
    toLeft(S[0], S[1], T[0])?
        // step forward at a left turn
        S.push(T.pop()):
        // or, backtrack
        S.pop();
}

Graham Scan: Correctness

Left Turn

Right Turn

9 号点被包含在了某一个三角形(1-8-10)的内部，它应该被排除掉。

Graham Scan: Analysis

Backtracks

Planarity

根据欧拉公式，平面图中所有边的数量包括面数加在一起依然和顶点数目保持同阶，边数不会超过顶点数的三倍。

Amortization

  if: S.size()++; T.size()--;   //  1 - 2
else: S.size()++;               // -1 + 0

Divide-And-Conquer (1)

Merge

归并排序作为引子引出我们的算法。

Divide-And-Conquer 要求我们接近均匀切分 divide，接着我们把这些结果合并起来成为有序序列，变成最终结果。

凸包问题也是如此，把输入的点集分成大小规模接近的子集分别求出它们的凸包。问题实质就变成了我有两个凸包子集之后如何将它们合并得到更大的凸包。

Common Kernel

找到一个公共核使得这两个待合并的子凸包能够同时关于这个点是角度有序的。

Interior

二路归并采用环形次序，然后 Graham Scan 即可。

Exterior

我们预选的那个来自第一个子凸包的 centroid point 不幸落在第二个子凸包的外面，在这种情况下我们应当如何完成二者的归并呢？

Divide-And-Conquer (2)

Preprocessing

不妨做一个假设，待合并的两个子凸包或者说它们对应的点集是沿着某个方向是可分割的，彼此独立。如果这样我们的合并任务就会变得更加简明、简单。

为了保证这一点，我们引入一个预处理：按 x 轴排序。

Common Tangents

Topmost + Bottommost?

Stitch

我们可以在最初构造一个子凸包的时候记下 leftmost 和 rightmost 各是哪两个顶点，剩下几乎不用花时间：把此前计算结果延续下来即可，而分摊到每一次合并常数时间就够了。

Zig-Zag

Related Posts