凸包

凸包（convex hull）是包含给定集合 $S$ 的最小凸集，记为 $\mathrm{conv}S$。集合凸，指任意两点之间的整条线段都在集合中。凸包因此把原点集之间需要的线段补齐，并继续补齐这些新点之间的线段。它不预先要求闭集，也不允许凸组合中的负系数。

对三点 $A=(0,0)$、$B=(4,0)$、$C=(0,3)$，凸包为填满的闭三角形，而不只是三条边。加入内部点 $P=(1,1)$ 不会改变凸包，因为原三角形已经包含它。

全部有限凸组合构成最小凸集

令 $C$ 为全部有限凸组合的集合： $$C=\{\sum _{i=1}^k{\lambda }_i{x}_i:k\ge 1,x_i\in S,{\lambda }_i\ge 0,\sum _i{\lambda }_i=1\}.$$ 取 $k=1$ 可见 $S\subseteq C$。若 $u,v\in C$，它们各有一组非负和为一的系数；对 $0\le t\le 1$，将两组系数分别乘 $t$ 与 $1-t$，得到 $tu+(1-t)v$ 的非负和为一表示，因此 $C$ 凸。

最后，任何包含 $S$ 的凸集都包含这些有限凸组合。对项数归纳：一项显然；多项时，若最后一个权重为一就回到一项，否则把前面的权重除以它们的和，先形成一个点，再与最后一点作两点凸组合。故 $C$ 包含于每个这样的凸集，正是最小者。这个论证给出了定义与计算表示之间的桥梁。

内部点可由三个顶点作凸组合；外部点被同一条线性不等式排除。

主例的三角形也可写为 $x\ge 0,y\ge 0,x/4+y/3\le 1$。若 $(x,y)$ 是顶点的凸组合，三个不等式均成立；反向若三式成立，取 ${\lambda }_B=x/4$、${\lambda }_C=y/3$、${\lambda }_A=1-x/4-y/3$，就得到非负和为一的表示。这证明两种描述完全相同。

对 $P=(1,1)$，权重为 $5/12,1/4,1/3$。变式取 $Q=(4,3)$，此时 $x/4+y/3=2>1$，故不在凸包中。只看到 $x,y$ 都介于顶点坐标的最小、最大值之间，不足以判定落在凸包内；包围矩形比三角形大。

Carathéodory定理与多余权重的消去

定理　在 ${ℝ}^d$ 中，凸包内的每个点都可表示为至多 $d+1$ 个原集合点的凸组合。

证明从任一有限凸组合 $x=\sum _{i=1}^k{\lambda }_i{x}_i$ 开始，先删掉零权重，令全部 ${\lambda }_i>0$。若 $k>d+1$，增广向量 $(x_i,1)\in {ℝ}^{d+1}$ 线性相关，所以存在不全为零的 ${\alpha }_i$，满足 $\sum _i{\alpha }_i{x}_i=0$、$\sum _i{\alpha }_i=0$。后一等式保证 ${\alpha }_i$ 同时有正有负。

选 $$t=\underset{{\alpha }_i>0}{min}\frac{{\lambda }_i}{{\alpha }_i}>0,{{\lambda }_i}^{\prime }={\lambda }_i-t{\alpha }_i.$$ 正 ${\alpha }_i$ 对应的新权重因最小值选择而非负，负 ${\alpha }_i$ 对应的权重反而增大；至少一个正项权重变为零。又有 $\sum _i{{\lambda }_i}^{\prime }=1$ 与 $\sum _i{{\lambda }_i}^{\prime }{x}_i=x$，所以表示的点不变，却减少了一个正权重点。重复有限次，直到只剩至多 $d+1$ 个点，证明完成。

二维中这个上界为三，说明任何凸包内点总能放进某个由原点集顶点组成的三角形，允许退化为线段或点；并不说固定选择的任意三个点都足够。若原点集的仿射维数只有一，上界还可缩为二。

闭性、顶点与仿射包

有限点集的凸包是紧集：系数位于闭有界的标准单纯形中，凸组合是连续映射，其像仍紧。因此主例的边和端点都包含在凸包中。一般点集却不能省去条件：取 $S=\{(t,0):0<t<1\}$，它本来就凸，所以凸包仍是开线段，不包含两个极限端点。若再取拓扑闭包，得到的才是闭凸包。

极点不能写为集合中两个不同点的严格凸组合。主例的三顶点为极点，$P$ 不是；它可由凸包中的其他点表示。有限点集凸包的极点来自原集合，但列出的每个原点未必都是极点。仿射包允许负权重，主例三个不共线点的仿射包为整个平面，远大于凸包。明确系数的符号限制，才能区分这两个对象。