凸包 · aiwiki.page

一个点集的凸包是包含这些点的最小凸集。在欧几里得空间中，凸性意味着：集合中任意两点之间的整条线段也属于该集合。对于平面上的有限个点，可以把凸包想象成一根橡皮筋绕过最外围的点并拉紧后所围成的区域。凸包包含围起来的整个区域，而不仅仅是它的边界。(cs.princeton.edu)

定义与数学表示

设 $S$ 是实向量空间的一个子集。它的凸包记作 $\operatorname{conv}(S)$ ，定义为

\operatorname{conv}(S) = \left\{ \sum_{i=1}^{m}\lambda_i x_i \;\middle|\; m\geq 1,\; x_i\in S,\; \lambda_i\geq 0,\; \sum_{i=1}^{m}\lambda_i=1 \right\}.

该定义中的每一个求和表达式都是一个凸组合，即权重非负且权重之和为一的加权平均。即使 $S$ 是无限集，也只需要考虑有限个点的组合。等价地，

\operatorname{conv}(S) = \bigcap_{\substack{C\supseteq S\\ C\text{ 为凸集}}}C.

因此，“最小”是就包含关系而言的：任何包含 $S$ 的凸集都包含 $\operatorname{conv}(S)$ 。(stanford.edu)

对于有限集 $S=\{p_1,\ldots,p_n\}\subseteq\mathbb R^d$ ，将各点作为列向量组成矩阵 $P$ 。一个点属于该凸包的条件便可表示为

x=P\lambda,\qquad \lambda_i\geq 0,\qquad \mathbf 1^{T}\lambda=1.

因此，判断给定点是否属于一个有限点集的凸包，是一个线性规划可行性问题。这可以直接由凸组合表示得出。(stanford.edu)

几何性质与有限点集

非空有限点集的凸包是一个凸多胞体，也就是有界的多面体。它的维数不一定等于所在空间的维数：三维空间中的共线点仍然只形成一条线段，而共面点形成的凸包则位于一个平面内。(stanford.edu)

典型例子包括：

单个点的凸包就是该点本身。
两个不同点的凸包是连接它们的线段。
平面上三个不共线点的凸包是它们确定的三角形，包括内部。
平面上不全共线的有限点集的凸包是一个凸多边形，包括内部。

对于平面上的有限点集，算法通常按顺时针或逆时针顺序列出凸包的顶点来表示凸包，而不是显式表示所围区域中的每一个点。(ti.inf.ethz.ch)

凸集的极点是指不能位于该集合中两个不同点之间的线段内部的点。有限点集凸包的极点就是其顶点。因此，位于某条边中间的边界点不是顶点；软件接口必须区分返回极点与返回边界上的全部输入点这两种情况。例如，CGAL 的平面凸包例程按逆时针顺序返回极点。(doc.cgal.org)

卡拉泰奥多里定理与闭包

卡拉泰奥多里定理（凸包）指出， $\mathbb R^d$ 的任意子集的凸包中，每个点都可以表示为该子集中至多 $d+1$ 个点的凸组合。因此，要表示平面凸包中的任意一个点，三个点就足够；在三维空间中，四个点就足够。这并不意味着整个凸包至多有 $d+1$ 个顶点：不同的点可能需要使用不同的子集来表示。证明利用向量 $(x_i,1)$ 之间的线性相关性，调整系数直到某个系数变为零，从而减少表示中使用的点数。(web.mit.edu)

讨论凸包时，还需要注意闭包（拓扑学）问题。 $\mathbb R^d$ 中紧集的凸包是紧集，但闭集的凸包不一定是闭集。闭凸包是 $\overline{\operatorname{conv}(S)}$ ，其中可能包含额外的极限点。对于有限集，这些区别不再存在，因为它们的凸包是紧集。(web.mit.edu)

对于紧集，其凸包也等于所有包含该集合的闭半空间的交。每个半空间都以一个超平面为边界，并取该超平面的一侧。这给出了通过不等式描述凸包的方法，与通过凸组合进行的描述互为补充。(ti.inf.ethz.ch)

算法与历史发展

计算有限点集的凸包是计算几何中的核心问题。对于平面输入，设 $n$ 为输入点数， $h$ 为凸包顶点数。不同算法组织点的方式各不相同，其时间复杂度是否依赖输出规模也有所区别。(cs.jhu.edu)

Graham 扫描法由罗纳德·格雷厄姆于 1972 年提出。它首先根据各点相对于某个极点的方向进行排序，然后依次扫描这些点，同时维护候选边界。造成向内转折的点会被移除。排序需要 $O(n\log n)$ 时间，随后的扫描则需要线性时间。这是早期达到最优时间复杂度的平面凸包算法之一。(cs.princeton.edu)

Andrew 单调链算法按坐标的字典序对点排序，然后分别构建下链和上链。与 Graham 扫描法一样，它的时间复杂度为 $O(n\log n)$ ，但不需要按极角排序。(algs4.cs.princeton.edu)

Jarvis 步进法又称礼品包装算法，它反复选择下一条支撑边，每一步都遍历输入点。其时间复杂度为 $O(nh)$ ，因此在凸包顶点较少时很有吸引力。Chan 算法发表于 1996 年，将较小分组的凸包与包装法相结合，在二维和三维情况下实现了 $O(n\log h)$ 的时间复杂度。这是一个输出敏感的复杂度界：计算量不仅取决于输入规模，也取决于结果的规模。(cs.jhu.edu)

在更高维空间中，输出包含各个面及其邻接关系，而不再只是一个按顺序排列顶点的多边形。Qhull 基于 Quickhull 算法，实现了多维凸包及相关几何结构的构建。(qhull.org)

方向测试与数值稳健性

平面凸包算法通常对三个点 $a,b,c$ 使用方向测试：

D=(b_x-a_x)(c_y-a_y) -(b_y-a_y)(c_x-a_x).

这个行列式在逆时针转向时为正，在顺时针转向时为负，在三点共线时为零。它使算法无需显式计算角度或三角函数，就能比较方向。(cs.princeton.edu)

使用浮点运算时，对于近乎共线或共面的点，舍入误差可能使符号判断不可靠。错误的几何判断可能破坏凸包的连接结构，导致面片翻转或邻接关系不一致。稳健的实现可以采用精确谓词、合并近乎共面的面片，或对输入施加微小扰动；这些方法对输出的影响各不相同。尤其需要注意的是，扰动法计算的是修改后坐标的凸包，而不是原始数据的精确凸包。(qhull.org)

重复点和低维输入也是实现中需要处理的情况。对于要求输入为满维多面体的接口，如果没有特殊处理，就不能把线段或平面凸包当作普通的三维实体。CGAL 的平面例程明确支持空凸包、单点凸包和线段凸包。(doc.cgal.org)

应用与局限

在数学优化中，凸包可以描述有限个备选方案的可行混合。凸包还将几何与线性可分性联系起来：两个非空的有限点类能够被一个超平面严格分离，当且仅当它们的凸包互不相交。凸包之间的距离出现在最大间隔分类和支持向量机的几何解释中。(stanford.edu)

凸包与德劳内三角剖分密切相关。将 $\mathbb R^d$ 中的点提升到抛物面上：

(x_1,\ldots,x_d) \longmapsto (x_1,\ldots,x_d,x_1^2+\cdots+x_d^2)

便可以从高一维空间中的下凸包恢复德劳内结构。同样，半空间求交也可以通过极对偶与凸包构建联系起来。(qhull.org)

凸包会有意舍弃非凸细节：它会填平凹陷和间隙，也不会保留内部点的排列。因此，它是一种包围式表示，而不是对任意形状的重建。高维还会带来另一种表示上的困难。例如， $d$ 维立方体只需 $2d$ 个不等式来定义，却有 $2^d$ 个顶点，因此其不等式表示与顶点表示的规模可能相差指数倍。(cs.princeton.edu)

参考来源

Convex Hullscs.princeton.edu
Convex Optimizationstanford.edu
Computational Geometry, CG 2012ti.inf.ethz.ch
Convex Analysis and Optimization Lecture Slidesweb.mit.edu
CGAL — 2D Convex Hulls and Extreme Points: User Manualdoc.cgal.org
ApproxDecompShapes.pdfcs.princeton.edu
Convex Hullalgs4.cs.princeton.edu
Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensionscs.jhu.edu