3.1 凸和凸包的定义
(Definitions of Convexity and Convex Hulls)

1. 如果对于集合 \(S\) 中的任意两点 \(x \in S, y \in S\)，都有线段 \(xy \subseteq S\)，则称集合 \(S\) 为凸集(convex)。这是凸性(convexity)的基本定义。 需要注意的是，该定义并未指定点的具体维度，也未说明 \(S\) 是否连通，有界或无界，闭集或开集。从图 3.1 可以看出， 任何带有"凹陷(dent)"的区域都不是凸集，因为可以找到两个点跨越该凹陷区域，使得它们所确定的线段存在区域外部的点。因此，任何具有凹顶点(reflex vertex)的多边形都不是凸集。
2. 线段 \(xy\) 是所有形如 \(\alpha x + \beta y\) 的点的集合，其中 \(\alpha ≥ 0, \beta ≥ 0\) 并且 \(\alpha + \beta = 1\)。 例如，线段中点 \(\frac{1}{2}(x + y)\) 的两个权重相等 \(\alpha = \frac{1}{2}, \beta = \frac{1}{2}\)。 线段端点有一个权重为 0。线段的这种代数(algebraic)表示方法在数学形式上和数值计算中都非常有用。作为后者的一个例子， 我们将用它来寻找两条线段的交点(7.2 节)。
3. 点集 \(x_1, \cdots, x_k\) 的凸组合是 \(\alpha_1 x_1 + \cdots + \alpha_k x_k\)，其中 \(\alpha_i ≥ 0\) 并且 \(\alpha_1 + \cdots + \alpha_k = 1\)。 因此，线段由其所有端点的凸组合构成的，三角形由其三个角的所有凸组合构成。在三维空间中，四面体由其四个角的凸组合构成。 凸组合引出了"重心坐标(barycentric coordinates)"的概念，我们将在第7章(7.3.1 节)中使用它。
4. 点集 \(S\) 的凸包(convex hull)是 \(S\) 中所有凸组合的集合。一些数学文献中将 \(S\) 的凸包记为 \(\text{conv} S\)，有时也会使用符号 \(\mathcal{H}(S)\)。 直觉上这样定义的凸包不可能有凹陷，但证明起来并不容易(参见练习 3.2.3[1])。
5. \(d\) 维空间中点集 \(S\) 的凸包是其中 \(d + 1\) 个(或更少)点的所有凸组合的集合。这与之前的定义的区别在于，它只需要使用 \(d + i\) 个点。 因此，二维集合的凸包是其三点子集的凸组合，如(3)所述，每个子集可以确定一个三角形。该定义与定义(4)等价，被称为 Caratheodory's 定理(Lay 1982, p. 17)。
6. 点集 \(S\) 的凸包是包含 \(S\) 的所有凸集的交集。这个定义或许比前两个定义更清晰，因为它不依赖于凸组合的概念。然而，"所有凸集(all convex sets)"的概念并不容易理解。
7. 点集 \(S\) 的凸包是包含 \(S\) 的所有半空间(halfspace)的交集。这可能是最清晰的定义，它与其他所有定义等价。 二维空间中的半空间就是半平面(halfplane)，它是一条直线及其一侧的所有点的集合。在更高维空间中，半空间是一个平面及其一侧的所有点的集合，以此类推。
   注意，一个集合的凸包是一个封闭的"实(solid)"区域，包含其内部的所有点。在计算几何中，人们常用它来更宽泛地指代该区域的边界，因为它是我们计算的边界，包含了整个区域。 我们将使用"在凸包上(on the hull)"来表示"在凸包的边界上(on the boundary of the convex hull)"。
8. 平面上有限点集 \(S\) 的凸包是包含 \(S\) 的最小凸多边形 \(P\)。所谓的最小，是指不存在其他多边形 \(P'\) 使得 \(P \supset P' \supseteq S\)。
9. 平面上有限点集 \(S\) 的凸包是，包围\(S\)的面积最小的凸多边形 \(P\)。
10. 平面上有限点集 \(S\) 的凸包是，包围\(S\)的周长最小的凸多边形 \(P\)。定义(9)和(10)与嵌套最小子集(8)的等价性在直觉上是显而易见的，但数学上却不显然(练习 3.2.3[6])。
11. 平面上点集 \(S\) 的凸包是由 \(S\) 中的点确定的所有三角形的并集。这只是上面(5)的重述，但其形式暗示了一种计算方法。

本章余下部分将重点讨论，二维空间中有限点集的凸包边界的构造算法。我们将从效率较低的算法(3.2节, 3.3节 和 3.4节 )入手， 逐步推导出最优算法(3.5节)， 最后考察可扩展到三维及更高维空间的算法(3.7节和 3.8节)。我们将只详细展示 Graham's 算法的所有细节， 并提供代码(3.5节)。

3.1.1. 极点(Extreme points)

在研究算法之前，我们有必要明确一下需求，定义算法的输出形式，特别是边界的构建。在第四章之前，我们先将注意力集中在二维空间，考察一个包含 \(n\) 个点的有限集合\(S\)。 我们可以识别出四种输出:

1. 所有在凸包上的点，并且是任意排序的。
2. 极点(extreme points)，任意排序。
3. 所有在凸包上的点，按照边界遍历的顺序。
4. 极点，按照边界遍历的顺序。

平面上点集 \(S\) 的极点extreme points是指凸包的顶点，这些顶点的内角严格凸的，小于 \(\pi\)。因此，我们只将"实际 real"顶点计为极点，凸包线段内部的点不被视为极点。 不同的应用可能需要不同的输出，例如，输出无序的凸包点((1) 和 (2))比对它们进行排序更容易。我们将在3.6节中看到， 在大 \(O\) 表示法下，这并不更容易。

我们首先关注输出(2)，识别处极值点。首先，注意到 \(S\) 的最高点，即 \(y\) 坐标最大的点，如果是唯一的则是极值点，或者恰好有两个高度相同的最高顶点，此时两个顶点都是极值点。 最低点、最右侧点和最左侧点的情况也类似。显然，一个点是极值点当且仅当存在一条经过该点且不与凸包相交的直线。然而，这种"存在性"的表述并不能直接给出计算方法。

因此，让我们来看看硬币的另一面，即非极点(nonextreme points)。