Carathéodory 定理

形式陈述 ​

设 $S\subseteq {\mathbb{R}}^d$。若

$$x\in \mathrm{conv}(S),$$

则存在 $S$ 中至多 $d+1$ 个点 $s_0,\dots ,s_d$，使

$$x\in \mathrm{conv}\{s_0,\dots ,s_d\}.$$

更精确地，若 $S$ 的仿射包公理库仿射空间Affine space忘去原点但保留向量平移作用和仿射组合的空间。维数为 $r$，则只需至多 $r+1$ 个点。集合 $S$ 可以无限；凸包公理库凸包Convex hull包含给定点集的最小凸集，是凸几何中的基本包络对象，并可进一步研究其算法构造。的定义本来就只使用有限凸组合，所以定理限制的是表示一个给定点所需的证人数量。

证明从任意有限表示

$$x=\sum _{i=1}^m{\lambda }_i{s}_i,{\lambda }_i\ge 0,\sum _{i=1}^m{\lambda }_i=1$$

开始。若 $m>r+1$，这些点仿射相关，故存在不全为零的实数 ${\mu }_i$ 满足

$$\sum _i{\mu }_i{s}_i=0,\sum _i{\mu }_i=0.$$

把 $\mu$ 整体变号后可假设某个 ${\mu }_i>0$，并令

$$t=\underset{{\mu }_i>0}{min}\frac{{\lambda }_i}{{\mu }_i}.$$

新系数 ${\lambda }_i^{\prime }={\lambda }_i-t{\mu }_i$ 仍非负、和为一，而且表示同一个 $x$；至少一个正系数变成零。删去该项并重复，最终只剩至多 $r+1$ 项。每一步都可核验地保持凸组合，而不是仅用“去掉冗余点”的图形直觉。

直觉 ​

在 $r$ 维仿射空间中，超过 $r+1$ 个点必有仿射冗余。沿一条系数和为零、加权点和也为零的方向移动凸组合系数，不会改变所表示的点；把移动量推到首次碰到系数零的位置，就能删除一个点而不离开概率单纯形。

定理不是说整个凸包只由同一组 $d+1$ 个点生成。不同的 $x$ 可以需要不同证人；它只把每个点的局部表示复杂度限制在环境维数以内。

例子与边界 ​

在平面中，任意凸包点都落在原集合某三个点的三角形内；若该点位于一条弦上，只需两个端点。单位正方形中心可写成一条对角线两端点的平均，因此实际证人数可以小于上界。

上界一般不能改成 $d$。取 ${\mathbb{R}}^d$ 中一个非退化 $d$-单纯形的 $d+1$ 个顶点，任一内部点都有全部重心坐标严格为正；若删去一个顶点，只剩一个真面，其凸包不含该内部点。由此 $d+1$ 是锐利界。

有限维假设不能无条件删除。无限维向量空间中，一个点仍由某个有限凸组合表示，但不存在统一的“维数加一”常数控制所有点。系数非负和总和为一也不可省略；允许任意仿射组合得到的是仿射包，允许任意线性组合则得到线性张成。

推论与应用 ​

Carathéodory 定理为凸几何提供小证书：判断点属于高维凸包时，总有一个至多 $d+1$ 点的见证。对有限点生成的多胞形公理库多面体与多胞形Polyhedron · Polytope分别由有限线性不等式交与有限点凸包描述，并由 Minkowski–Weyl 定理连接的凸几何对象。，它限制单个点所需的顶点数，也解释线性规划基本解为何由有限个活跃方向控制。

本定理与Radon 定理公理库Radon 定理Radon theorem欧氏 d 维空间中的任意 d 加二个点都能划分为两个凸包相交的非空部分。都由仿射相关性驱动：前者沿相关方向消去凸组合项，后者按相关系数的正负把点集分成两个凸包相交的部分。二者结论不同，不能把“少量点表示”与“两个凸包相交”合并成一句同义口号。

参考资料

• Alexander Barvinok, A Course in Convexity, American Mathematical Society, 2002, Ch. 1, Carathéodory’s theorem.
• Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002, Ch. 1, convexity theorems.