3.2 极点的朴素算法
(Naive Algorithms for Extreme Points)

本节内容将略有偏离主题，只会引出一些速度较慢的算法。但它们将作为后续更快算法的参照。

3.2.1. 非极点(Nonextreme Points)

显然，识别出非极点就足以识别出极点。

点集 \(S = \{p_0, p_1, \cdots, p_{n-1} \}\) 中所有点都不相同，根据该引理，可以直接得到算法 3.1。可以用三次 LeftOns 实现在三角形内的测试。 值得注意，这里无需检查引理的第二条规定，即 \(p_l\) 不是三角形的顶点。因为我们假设 \(S\) 的点各不相同，并且在循环中排除了 \(i,j,k\) 作为 \(l\) 的循环索引，所以该条件一定满足。

该算法的时间复杂度显然是 \(O(n^4)\) 的，因为它嵌套了四层循环，每层循环的时间复杂度为 \(O(n)\)。对于 \(n^3\) 个三角形中的每一个，非极点测试的时间复杂度为 \(n\)。 要想找到一个更慢的算法还挺难的。

3.2.2. 极边(Extreme Edges)

识别出极边要相对容易一些，极边是凸包的边。如果 \(S\) 中的每个点都在由某条边确定的线段上或一侧，则该边是极边。 看起来最简单的检测方法就是，将边看做是有方向的，并指定两个可能方向中的一个来确定"侧"。假设有向边的左侧为内侧。 如果存在某个点既不在该边的左侧也不在该边上，则该有向边不是极边。这就是我们在下面的伪代码中使用的规则。

遗憾的是，该算法输出的是所有在凸包上的点，而不是极点。假设 \(xy\) 是一条极边，点 \(z\) 位于线段 \(xy\) 的内部。那么 \(xz\) 和 \(zy\) 都具有极边的性质，它们的右侧没有点， 也就是说，没有点既不在其左侧也不在其上。但实际上，它们都不应该算作极边，并要求极边的两个端点都必须是极点顶点(extreme vertices)。

我们选择不在下面检查这个确切的条件(因为我们只是为了改进这个算法而探讨这个算法的框架)。因此，算法 3.2 只针对"一般位置(in general position)"的点集输出极点，其中没有三点共线。 显然该算法的时间复杂度为 \(O(n^3)\)，因为它有三个嵌套循环，每个循环的时间复杂度为\(O(n)\)。对于 \(n^2\) 对点中的每一对，极边测试的时间复杂度为 \(n\)。 现在可以很容易地找到哪些顶点是极端点(在一般位置假设下)，因为极点是极边的两个端点。

3.2.3. 练习

1. 凸包的凸性Convexity of the convex hull。根据3.1 节定义列表的第4项， 点集 \(S\) 的凸包是集合中各点的所有凸组合的集合，证明 \(\text{conv}S\) 实际上是凸的，因为连接任意两点的线段都在 \(\text{conv}S(1)\) 中。
2. [Programming] 实现极点算法Extreme point implementation。以一个点列表作为输入，并按任意顺序打印其中极点。尽量编写最短、最简单的代码，无需考虑运行时间。 可以利用第一章三角分割代码中的函数 ReadPoints 读取点(这些点是否构成多边形无关紧要)，Left 和 LeftOn(代码 1.6)等等。
3. 最小支撑线Min supporting line(Modayur 1991)。假设有一个凸包算法可以使用，设计一个算法，找出一条直线 \(L\)，使得:
   1. 给定集合中的所有点都位于直线 \(L\) 的一侧
   2. 各点道直线 \(L\) 的垂直距离最小
4. 仿射包Affine hulls。一组点 \(x_1, \cdots, x_k\) 的仿射组合affine combination是形如 \(\alpha_1 x_1 + \cdots + \alpha_k x_k\) 的和， 其中 \(\alpha_1 + \cdots + \alpha_k = 1\)。注意，该定义与凸组合的定义(3) 不同， 它缺少条件 \(\alpha_i ≥ 0\)。在二维空间中，两个点的仿射包是什么? 三个点的呢? \(n > 3\) 个点的呢? 在三维空间中，两个点的仿射包是什么?三个点的?四个点的? \(n > 4\) 个点的?
5. 极边Extreme edges。修改算法 3.2，使其无需一般位置假设也可正确运行。
6. 最小面积的凸多边形Minimum area, convex。证明3.1 节的特征(9)，包含一组点的，面积最小的凸多边形， 就是这些点的凸包。
7. [easy] 最小面积的非凸多边形 Minimum area, nonconvex。通过具体例子证明，包围一组点的最小面积多边形(可能是非凸的)可能不是这些点的凸包。
8. 最短路径Shortest path below。给定一个点集 \(S\) 和另外两个点 \(a,b\)。其中 \(a\) 在 \(S\) 的左侧，\(b\) 在 \(S\) 的右侧。 设计一个算法，找到从 \(a\) 到 \(b\) 的最短路径，该路径需要避开 \(S\) 的内部。假设可以使用凸包算法。