KNOWECON WIKI

ARTICLE

凸包

凸包 (Convex Hull) 凸包（Convex Hull）是计算几何与凸分析中最基础的概念之一，指包含给定点集的最小凸集。给定 R^d 中的点集 S = \ p_1, p_2, , p_n\，其凸包 conv(S) 定义为所有包含 S 的凸集的交集，等价于 S 中所有点的凸组合的集合： 在二维平面上，凸包可以直观地想象为：将点集中的所有点视为钉子，用一

浏览 0 更新 2025-10-26

凸包 (Convex Hull)

凸包（Convex Hull）是计算几何与凸分析中最基础的概念之一，指包含给定点集的最小凸集。给定 Rd\mathbb{R}^d 中的点集 S={p1,p2,…,pn}S = \{\mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_n\}，其凸包 conv⁡(S)\operatorname{conv}(S) 定义为所有包含 SS 的凸集的交集，等价于 SS 中所有点的凸组合的集合：

conv⁡(S)={∑i=1nλipi  |  λi≥0,  ∑i=1nλi=1}\operatorname{conv}(S) = \left\{ \sum_{i=1}^{n} \lambda_i \mathbf{p}_i \;\middle|\; \lambda_i \geq 0, \; \sum_{i=1}^{n} \lambda_i = 1 \right\}

在二维平面上，凸包可以直观地想象为：将点集中的所有点视为钉子，用一根橡皮筋从外部将其紧紧箍住，橡皮筋所形成的多边形边界即为凸包。这是一个最小凸多边形，其顶点必为 SS 中的点，且 SS 中的所有点要么在边界上，要么在内部。

数学性质

凸包具有以下核心性质：

  • 凸性：凸包是凸集，即任意两点连线段完全包含于凸包内。
  • 最小性：凸包是所有包含 SS 的凸集中最小的（按集合包含关系）。
  • 极值点：凸包的顶点是 SS 的极值点（不能表示为 SS 中其他点凸组合的点）。
  • Carathéodory定理：若 S⊂RdS \subset \mathbb{R}^d，则凸包中的任意一点都可表示为 SS 中至多 d+1d+1 个点的凸组合。
  • 分离定理：凸包外的任意一点都可以由一条直线（超平面）与凸包分离，这是支撑超平面定理的直接推论。

计算算法

二维凸包的计算是计算几何的经典问题，主要有以下算法：

Graham扫描法 (Graham Scan)

时间复杂度 O(nlog⁡n)O(n \log n)。步骤为：选取最左下点作为基点 p0p_0；按极角对所有点排序；用一个栈依次处理每个点，若当前点与栈顶两点构成的转向为"右转"（非逆时针），则弹出栈顶，重复此过程直至呈左转；最终栈中的点构成凸包的顶点序列。Graham扫描充分利用了极角排序和栈结构，实现简洁高效。

Jarvis步进法 (Jarvis March / 礼品包裹算法)

时间复杂度 O(nh)O(nh)，其中 hh 为凸包顶点数。从最左点出发，每次选择使极角最小的点作为下一个凸包顶点，绕一圈回到起点。当 h≪nh \ll n 时优于Graham扫描，是输出敏感型算法。

分治法与QuickHull

分治法将点集按 x 坐标递归二分，分别求子集凸包后合并（类似归并排序）。QuickHull 思路类似快速排序：找到端点连线两侧最远的点构成三角形，递归处理三角形外的点集，期望 O(nlog⁡n)O(n \log n)。

三维及以上凸包的计算通常通过增量法或随机增量算法完成，期望复杂度 O(nlog⁡n)O(n \log n)（三维）或 O(n⌊d/2⌋)O(n^{\lfloor d/2 \rfloor})（高维）。

经济学中的应用

凸包在经济学中有丰富的应用场景：

  1. 生产可能性边界 (PPF)：在给定资源和技术约束下，经济体所能生产的所有商品组合的集合。PPF 的外边界本质上就是可行生产集凸包的边界，其凹性（凸向原点）对应边际转换率递增。
  2. 数据包络分析 (DEA)：用于评估决策单元（如企业、学校）的相对效率。DEA 构造观测数据点的凸包（前沿面），位于前沿面上的单元为技术有效（效率=1），内部单元为非有效。这一非参数方法无需预设生产函数形式，广泛应用于绩效评估和基准分析。
  3. 风险资产组合：在均值-方差分析中，nn 种风险资产的所有可行组合构成一个凸集，其左上边界（最小方差前沿）即为该凸集凸包的一部分。有效前沿是凸包边界上均值最大化的子集。
  4. 博弈论中的相关均衡：相关均衡的集合是纳什均衡集合的凸包，这一几何事实揭示了引入相关信号如何扩展均衡可能性空间。
  5. 显示偏好理论：观测到的消费束的凸包可用于检验消费者选择是否满足显示偏好的弱公理 (WARP) 或强公理 (SARP)，为理性假设的检验提供几何工具。

与凸分析的关系

在更抽象的层面上，凸包是凸分析的起点。Krein-Milman定理指出：任何紧凸集等于其极值点集合的闭凸包。这一结果将凸性结构的研究归结为对极值点的分析。在无穷维空间中（如泛函分析），凸包的闭包性质支撑着Hahn-Banach定理和Kakutani不动点定理等核心结论，进而渗透至一般均衡理论对均衡存在性的证明中。

凸包作为几何最基础的操作之一，不仅连接了计算几何、优化理论和经济学，更提供了一个将离散数据转化为连续结构、从而进行全局分析的通用语言。