凸包

形式陈述 ​

集合 $S\subseteq {\mathbb{R}}^d$ 的凸包首先是一个凸几何对象：它由 $S$ 的所有有限凸组合组成，

$$\mathrm{conv}(S)=\{\sum _i{\lambda }_i{x}_i:{\lambda }_i\ge 0,\sum _i{\lambda }_i=1\},$$

等价于包含 $S$ 的所有凸集之交。有限平面点集的凸包是可能退化的凸多边形。计算页面通常以极点序列表示它，并需约定是否保留共线边界点；这种输出接口不改变凸包作为最小凸集的定义。

直觉 ​

凸包是包含点集的最小凸集，可想成套住所有点的橡皮筋收紧后留下的边界。它丢弃不影响外轮廓的内部点，却保留所有线性方向上的极值，因此既是几何包络，也是许多优化问题的充分摘要。关键条件是凸组合系数非负且和为一；若允许任意线性组合，得到的是仿射包而非凸包。

例子与边界 ​

三角形三个顶点的凸包是整个三角形，内部点不改变结果。更具体地，点集 $(0,0),(1,0),(1,1),(0,1),(1/2,1/2)$ 的凸包是单位正方形，中心点不成为顶点，因为它可写成四个角点的凸组合。Graham scan 先按极角排序，再用方向判定维护左转栈，在比较/实数 RAM 模型下给出确定性最坏 $O(n\log n)$；单调链达到同一界。若输出极点数为 $h$，输出敏感算法可以达到 $O(n\log h)$，所以只报一个输入规模有时会掩盖更细的保证。

若所有点共线，凸包退化为两端点之间的线段；只有一个不同点时则退化为单点，而不是二维多边形。边界上其余共线点是否全部输出取决于 API 约定：几何对象的极点只有端点，但某些算法题要求保留所有边界输入点。重复点、浮点近共线和输入顺序也必须显式处理。

推论与应用 ​

凸包建立在凸集公理库凸集Convex set任意两点间线段全部包含在集合中的向量空间子集。与有限点集公理库有限集Finite set与某个初始自然数段存在双射的集合。上，常由方向判定公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。驱动 Graham scan 或 monotone chain；共线与重复点要求精确谓词和明确 tie-breaking。随机增量构造公理库随机增量构造randomized incremental construction · RIC按随机排列插入对象，以冲突关系和反向分析控制几何结构的期望构建成本。提供期望分析的另一条路线，但随机排列的期望界不能写成确定性最坏界。数据超出内存时应在外存模型公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。下计块传输，并行实现则按并行模型公理库并行算法模型parallel algorithm model · parallel computation model用总工作、关键路径、处理器数和通信成本共同描述并行算法，而不只报告理想加速比。分别报告工作与深度。

凸包边界上的站点对应Voronoi 图公理库Voronoi 图Voronoi diagram · Voronoi tessellation按到有限站点集中的最近距离把度量空间划分为闭合单元及其公共边界。的无界 cell，Delaunay 三角剖分公理库Delaunay 三角剖分Delaunay triangulation以空外接圆条件或 Voronoi 邻接刻画有限平面点集的几何三角剖分。覆盖同一凸包。在线性目标上，最优点可在极点中寻找；碰撞检测、形状摘要和几何对偶也使用这一外壳。

参考资料

• 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。