形式陈述

集合 $S\subseteq\mathbb R^d$$S\subseteq {\mathbb{R}}^d$ 的凸包是所有有限凸组合的集合

$$ \operatorname{conv}(S)=\left\{\sum_i\lambda_i x_i:\lambda_i\ge0,\ \sum_i\lambda_i=1\right\}, $$$$\mathrm{conv}(S)=\{\sum _i{\lambda }_i{x}_i:{\lambda }_i\ge 0,\sum _i{\lambda }_i=1\},$$

等价于包含 $S$$S$ 的所有凸集之交。有限平面点集的凸包是可能退化的凸多边形；输出通常只列极点，并需约定是否保留共线边界点。

直觉

用橡皮筋套住所有点，松开后形成的边界就是凸包；内部点不会影响外轮廓。

例子与边界

三角形三个顶点的凸包是整个三角形，内部点不改变结果。Graham scan 先按极角排序，再用方向判定维护左转栈，时间 $O(n\log n)$$O(n\log n)$；单调链同样达到该界。所有点共线时凸包是一条线段而非二维多边形。

推论与应用

凸包用于碰撞检测、形状摘要、线性优化、支持函数和几何对偶，也是许多高维几何算法的基本外壳。

参考资料

• Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008，Chs. 1–7。
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。