凸包

在几何学中，形状的凸包或凸包络或凸闭包是包含它的最小凸集。 凸包可以定义为包含欧几里德空间给定子集的所有凸集的交集，或者等效地定义为子集中所有凸点组合的集合。 对于平面的有界子集，凸包可以可视化为由围绕子集拉伸的橡皮筋包围的形状。

开集的凸包是开的，紧集的凸包是紧的。 每个紧致凸集都是其极值点的凸包。 凸包算子是闭包算子的一个例子，每个反拟阵都可以通过将这个闭包算子应用于有限的点集来表示。寻找平面或其他低点的有限点集的凸包的算法问题 维欧几里德空间及其相交半空间的对偶问题是计算几何的基本问题。 对于二维或三维点集，它们可以在 O ( n log ⁡ n ) {displaystyle O(nlog n)} 时间内解决，并且及时匹配上界定理给出的最坏情况输出复杂度 在更高的维度。

与有限点集一样，凸包也被研究用于简单的多边形、布朗运动、空间曲线和函数的 epigraphs。 凸包在数学、统计学、组合优化、经济学、几何建模和动物行为学中有着广泛的应用。 相关结构包括正交凸包、凸层、Delaunay 三角剖分和 Voronoi 图以及凸头骨。

如果欧几里德空间中的一组点包含连接其每对点的线段，则它被定义为凸的。 给定集合 X {displaystyle X} 的凸包可以定义为

• 包含 X {displaystyle X} 的（xxx）最小凸集
• 包含X {displaystyle X}的所有凸集的交集
• X {displaystyle X}中点的所有凸组合的集合
• 所有单纯形与 X {displaystyle X} 中的顶点的并集

对于欧几里德平面中的有界集合，并非都在一条线上，凸包的边界是最小周长包含 X {displaystyle X} 的简单闭合曲线。 可以想象拉伸一根橡皮筋使其围绕整个集合 S {displaystyle S} 然后松开它，让它收缩； 当它变紧时，它包围了 S {displaystyle S} 的凸包。 该公式不会立即推广到更高维度：对于三维空间中的有限点集，点的生成树的邻域以任意小的表面积包围它们，小于凸包的表面积。 然而，在更高的维度中，寻找给定形状上方的最小能量表面的障碍物问题的变体可以将凸包作为它们的解决方案。

对于三维物体，xxx个定义指出凸包是物体的最小可能凸边界体积。使用凸集交集的定义可以扩展到非欧几里德几何，使用凸组合的定义可以扩展 从欧氏空间到任意实向量空间或仿射空间； 凸包也可以以更抽象的方式推广到定向拟阵。

xxx个定义是否有意义并不明显：为什么对于每个 X {displaystyle X} 应该存在一个包含 X {displaystyle X} 的xxx最小凸集？ 然而，第二个定义，即包含 X {displaystyle X} 的所有凸集的交集，是明确定义的。 它是所有其他包含 X {displaystyle X} 的凸集 Y {displaystyle Y} 的子集，因为 Y {displaystyle Y} 包含在相交的集合中。 因此，它正是包含 X {displaystyle X} 的xxx最小凸集。 因此，前两个定义是等价的。

每个包含 X {displaystyle X} 的凸集必须（假设它是凸的）包含 X {displaystyle X} 中点的所有凸组合，因此所有凸组合的集合包含在所有 包含 X {displaystyle X} 的凸集。 相反，所有凸组合的集合本身就是一个包含 X {displaystyle X} 的凸集，因此它也包含所有包含 X {displaystyle X} 的凸集的交集，因此第二个和第三个定义是等价的 .

事实上，根据 Carathéodory 定理，如果 X {displaystyle X} 是 d {displaystyle d} 维欧几里得空间的子集，则 X {displaystyle X} 中有限多个点的每个凸组合 也是 X {displaystyle X} 中至多 d + 1 {displaystyle d+1} 点的凸组合。