凸多面体是欧几里得空间中由有限个线性不等式定义的区域。每个不等式确定一个闭半空间,因此它们的交是一个凸集:连接区域内任意两点的线段都完全位于该区域内。在经典三维几何学中,凸多面体通常指由有限个平面多边形面围成的有界立体。在优化理论和现代凸几何中,它也包括无界区域和低维对象。有界的凸多面体称为凸多胞体。
定义与约定
在 中,凸多面体具有如下形式:
其中,每个 都是向量,每个 都是实数,圆点表示欧几里得点积。等价地,
其中 是一个矩阵,不等式按分量理解。
对于非零向量 ,方程 定义一个超平面,而相应的不等式选取该超平面两侧的两个闭半空间之一。因此,凸多面体总是闭集,但不一定有界。
术语的含义取决于语境:
- 在初等立体几何中,凸多面体通常是有界的,且在三维空间中具有非空内部。
- 在凸分析和线性规划中,多面体可以无界、为空,也可以包含在一个低维仿射子空间中。
- 多胞体是有界的,其维数可以是任意有限值。三维凸多胞体就是传统上所称的凸多面体这一有界对象。
多面体一词也有更广泛的用法,可以指多面体曲面和非凸立体。因此,凸性是一项不可缺少的限定条件,并非所有称为多面体的对象都自动具有这一性质。
等价表示
凸多面体既可以用不等式描述,也可以用生成元描述。
半空间表示
描述 称为 H 表示。对于一个立方体,
其中的六个不等式描述了立方体六个面的支撑平面。
一种表示中可能含有冗余不等式:去掉其中某个不等式,所表示的集合可能保持不变。对于满维多面体,无冗余的不等式表示中,每个不等式对应一个面维数比多面体低一维的面,即一个刻面。
顶点表示
每个非空有界凸多面体都是有限个点的凸包:
因此,每个点 都可以写成一个凸组合:
这些生成点可以恰好取为所有顶点。
例如,上述立方体也是八个点 的凸包。
闵可夫斯基–外尔定理将这种等价性推广到无界多面体。每个非空多面体都可以写成
其中
加号表示将第一个集合中的点与第二个集合中的点相加。向量 描述多面体向无限远延伸的方向。相反的两个方向可以表示一整条直线,因此该定理也适用于没有顶点的多面体。
面、棱与顶点
支撑超平面与凸多面体相交,同时使整个多面体位于其一侧。它与多面体的交集是一个面。更一般地,非空面可以描述为某个线性泛函在多面体上取得最大值的所有点组成的集合,前提是该最大值确实能够取得。
对于满维的三维凸多面体:
- 顶点是零维面。
- 棱是一维面。
- 刻面是二维面,在初等几何中通常简称为面。
在有界凸多面体中,每个刻面都是凸多边形,每条棱恰好属于两个刻面,每个顶点至少有三条棱相交。顶点是一个极点:它不可能严格位于连接多面体内两个不同点的线段之间。
在抽象的面集合中,通常也包括空面和整个多面体。按包含关系排序后,这些面构成一个面格,它记录各面之间的关联关系,而不涉及长度或角度。
因此,两个多面体可以具有相同的组合结构,却具有不同的几何形状。立方体和长方体的顶点、棱和面可以一一对应,尽管它们的棱长可能不同。
欧拉公式与组合结构
对于任意有界的三维凸多面体,设 、 和 分别表示顶点数、棱数和刻面数,则
这就是与莱昂哈德·欧拉相关联的欧拉多面体公式。其拓扑学解释是:多面体的边界与球面同胚,而球面的欧拉示性数为 。
每个面至少有三条棱,每个顶点的度至少为三。对关联关系进行计数可得
结合欧拉公式,可推出
第一个不等式取等号,当且仅当每个刻面都是三角形;第二个不等式取等号,当且仅当每个顶点恰好有三条棱相交。
顶点和棱构成多面体的棱图,这是图论研究的对象。施泰尼茨定理指出,有限简单图是某个有界三维凸多面体的棱图,当且仅当它是平面图且为三顶点连通图。平面性是指该图可以画在平面上而不使边相交;三顶点连通性是指删除任意两个顶点后,图仍然连通。
重要类别
正凸多面体
柏拉图立体,即正凸多面体,恰好有五种:
| 立体 | 顶点数 | 棱数 | 面数 | 面的形状 |
|---|---|---|---|---|
| 正四面体 | 4 | 6 | 4 | 等边三角形 |
| 立方体 | 8 | 12 | 6 | 正方形 |
| 正八面体 | 6 | 12 | 8 | 等边三角形 |
| 正十二面体 | 20 | 30 | 12 | 正五边形 |
| 正二十面体 | 12 | 30 | 20 | 等边三角形 |
其正则性既要求各面为正多边形,也要求各顶点周围的面的排列方式一致。大多数凸多面体不具备这两种性质中的任何一种。
单纯形多面体与简单多面体
有界三维凸多面体的每个刻面若都是三角形,就称其为单纯形多面体;若每个顶点恰好有三条棱相交,就称其为简单多面体。
正八面体和正二十面体是单纯形多面体;立方体和正十二面体是简单多面体。正四面体则兼具这两种性质。在 维情形中,相应的定义分别要求每个刻面都是单纯形,以及每个顶点恰好关联 条棱。
棱柱与棱锥
将一个凸多边形平移到与其所在平面平行的平面上,并连接对应点,就得到一个凸棱柱。凸棱锥则是一个凸多边形与其所在平面外一点的凸包。
这些构造产生了无穷多个多面体类别。它们的底面不必是正多边形,侧棱也不必垂直于底面。
对偶性与刚性
对于内部包含原点的有界满维凸多面体 ,其极体为
极体仍然是有界满维凸多面体,并且
极性变换会反转面之间的包含关系。在三维空间中,顶点对应刻面,棱对应棱,刻面对应顶点。因此,立方体与正八面体互为对偶,正十二面体与正二十面体互为对偶,而正四面体在组合意义下是自对偶的。简单多面体与单纯形多面体在对偶变换下相互转换。
凸性还带来了很强的度量约束。奥古斯丁-路易·柯西于1813年证明的柯西刚性定理指出,两个凸多面体如果对应面分别全等,并且具有相同的关联结构,那么这两个多面体全等。通俗地说,一个闭合凸多面体曲面在其多边形面保持刚性的情况下,不能发生挠曲。非凸多面体并不普遍满足同样的刚性结论。
历史
古希腊数学家已经研究过正凸多面体。《几何原本》第十三卷构造并比较了五种正多面体。
欧拉在十八世纪对顶点数、棱数和面数的研究,推动了研究重心从个别形状转向一般结构性质。柯西刚性定理确立了另一类约束,将各面的几何性质与整个立体的形状联系起来。
十九世纪和二十世纪期间,对凸体、线性不等式组和高维多胞体的研究逐渐发展为统一的理论。在二十世纪,线性规划使多面体成为数学优化的核心研究对象,而施泰尼茨定理则将三维凸多面体与平面图联系起来。
应用与局限
在数学优化中,线性约束定义了一个多面体可行集。如果该区域非空且有界,线性目标函数就在某个顶点处取得最优值,不过一整条棱、一个面乃至整个区域也可能都是最优解所在之处。这一事实是基于顶点的优化方法的基础。
在整数规划中,可行整数点的凸包为离散问题提供了几何模型。描述或逼近这些凸包的线性不等式,为松弛方法和割平面方法提供了支持。
凸多面体也用于计算机图形学、碰撞检测和工程中的几何建模。其半空间描述使点的包含性检验十分直接:一个点位于多面体内,当且仅当它满足所有定义不等式。包括有限元法在内的数值方法中,也使用多面体网格。
凸多面体的用途存在若干局限:
- 凸性排除了空腔和凹陷。 更复杂的立体需要采用非凸表示,或分解成若干凸块。
- 平面面片只能逼近曲面边界。 要提高几何精度,通常就需要增加面的数量。
- 等价表示的规模可能相差悬殊。 在维数可变的情形中,简短的不等式表示可能对应指数级数量的顶点,反之亦然。
- 数值退化可能使计算复杂化。 近乎共面的面和近乎重合的顶点需要谨慎的几何检验;否则,舍入误差可能导致面的结构不一致。