多胞形是一种几何对象,将二维的多边形和三维的有界多面体推广到任意有限维空间。按照现代最常用的定义,凸多胞形是实欧几里得空间中有限个点的凸包。等价地,它是有限个闭半空间的有界交集。这两种描述方式——一种通过点,另一种通过不等式——将其几何形状与代数表示和计算联系起来。
多胞形是几何学、组合数学和数学优化中的基本对象。它们的各个面刻画了有限的关联结构;它们的体积和格点将几何与算术联系起来;它们的边则描述了重要优化算法中可采取的移动步骤。常见的例子包括三角形、立方体和四面体,而高维多胞形还可以表示概率分布、运输方案、调度安排以及离散优化问题的解。
术语的含义随语境而异。在凸几何中,“多胞形”通常专指上述凸且有界的对象。其他分支则研究非凸多胞形、星形多胞形或抽象多胞形;在这些研究中,关联关系和对称性可能比空间中的实体区域更为重要。除非另有说明,下文讨论的均为非空凸多胞形。
定义与有限表示
设 为 中的点。它们的凸包为
具有这种形式的集合称为多胞体。 中的每一点都是这些生成点的凸组合,且连接 中任意两点的线段都完全包含在 中。因此,每个凸多胞体都是凸集。某些生成点可能是冗余的:在定义所用的点列中加入一个内部点,并不会改变其凸包。
与之等价的不等式表示形式为
前提是这个集合有界。这里, 是实矩阵,其中每一行确定一个闭半空间。等式可以用一对方向相反的不等式表示,不过在计算中,保留独立的等式往往更为合适。一般而言,有限个闭半空间的交集称为多面体,它不一定有界。例如,非负卦限是多面体,却不是多胞体。有限凸包表示与有界不等式表示之间的等价性,是闵可夫斯基–外尔定理的一项基本推论。
的维数是其仿射包的维数;仿射包是包含它的最小仿射空间。因此,嵌入 中的三角形是二维的,而不是三维的。当多胞体的仿射包就是整个环境空间时,称其为满维多胞体。许多定理在仿射包内表述最为自然,因为低维多胞体在其仿射包内就成为满维的。特别地,多胞体的相对内部由相对于该仿射包而言的内部点组成。
凸多胞体是闭且有界的,因此是紧致的。它们只有有限个顶点,并且恰好是这些顶点的凸包。相比之下,圆盘虽然是紧致的凸集,却不是多胞体:它的圆周边界上有无穷多个极点。因此,有界性与有限生成性是定义中两个独立的方面,而不是仅由凸性就能推出的性质。
两种标准数据格式体现了上述等价定义。V-表示列出顶点或其他生成点,H-表示则列出线性不等式,以及必要时的等式。从数学原理上说,这两种格式之间的转换是直接的,但计算代价可能很高。一个多胞体可能顶点相对较少而有非常多的刻面,也可能恰好相反,因此一种表示的规模可能比另一种大出指数级。
面、关联关系与局部结构
多胞体 的非空真面是某个非常值线性泛函取得最大值的点集:
从几何上说,一个支撑超平面与多胞体相接,而不穿过其相对内部;它与多胞体的交集就是一个面。按惯例,空面和 本身也算作面。每个非空面也都是多胞体。
维数为 、 和 的面分别称为顶点、棱和二维面。对于 维多胞体,维数为 的面称为刻面,维数为 的面称为脊。三维立方体有八个顶点、十二条棱和六个刻面。在四维多胞体中,刻面是三维多面体,因此“面”一词并不限于平坦的多边形面片。
所有面按包含关系排序,构成面格。这一结构记录了哪些顶点位于哪些棱上、哪些棱包含在哪些高维面中,等等。若两个多胞体的面格同构,就称它们组合等价。这一条件比全等或仿射等价更弱:正方形与非矩形的凸四边形虽然边长和角度不同,却具有相同的面格。因此,面格将关联关系信息与具体的几何实现区分开来。
顶点附近的局部结构可以借助顶点图形来研究。选取一个将某个顶点与其余所有顶点分隔开的超平面,并使它充分靠近该顶点,就能将多胞体截出一个 维多胞体。这个截面的各个面对应于原多胞体中包含该顶点的面,维数则降低一维。立方体的顶点图形是三角形,八面体的顶点图形是正方形。这一构造将有关顶点邻域的问题转化为低维多胞体理论中的问题。
若一个 维多胞体的每个顶点都恰好位于 条棱上,等价地,恰好位于 个刻面上,就称它为简单多胞体。若每个刻面都是单纯形,就称它为单纯多胞体。立方体是简单多胞体,八面体则是单纯多胞体。这两个条件互为对偶,而非同义;单纯形同时满足这两个条件。
多胞体的顶点和棱构成它的图,这是图论的研究对象。巴林斯基定理指出, 维多胞体的图是 顶点连通的:删除少于 个顶点不会使图失去连通性。在三维情形下,施泰尼茨定理给出了完整的图论刻画:一个有限图是某个三维凸多胞体的图,当且仅当它是平面图且为三顶点连通图。
基本族与对称性
单纯形是每个维度中最小的满维多胞形。一个 -单纯形是 个仿射无关点的凸包。它在低维中的例子依次是线段、三角形和四面体。其顶点的每个子集都确定一个面,因此它的 维面数为
单纯形尤为重要,因为较复杂的多胞形可以剖分为单纯形,而且单纯形上的仿射坐标为表示插值和概率权重提供了一种自然的方法。
超立方体和交叉多胞形构成另一对基本多胞形。它们的标准坐标模型为
其中 为坐标单位向量。超立方体有 个顶点和 个维面;交叉多胞形有 个顶点和 个维面。在三维空间中,它们分别是立方体和八面体。更一般地,超立方体的 维面数为
:选出 个可自由变化的坐标,再将其余每个坐标固定在两个端点之一,即得到一个这样的面。
正多胞形的对称群在其旗上具有传递作用,其中,旗是由相互关联的面组成的极大链。在欧几里得几何中,这里所说的对称是保持距离的变换,其结构通过群论来研究。二维空间中有无穷多种正凸多边形,三维空间中有五种正凸多面体,四维空间中则有六种正凸多胞形。四维中的例外类型包括正二十四胞体、正一百二十胞体和正六百胞体。在五维及以上的每个维度中,正凸多胞形都只剩下三种类型:单纯形、超立方体和交叉多胞形。
正则性比维面全等或各顶点外观相同的条件严格得多。各方向棱长不全相等的长方体具有与立方体相同的组合类型,却不具备立方体完整的欧几里得对称性。反过来,面格的组合自同构也未必都能实现为某个特定几何嵌入的等距变换。对于抽象多胞形,几何对称性与组合对称性之间的区别尤其重要。
若干对称性较低的多胞形族也在结构上发挥着重要作用。循环多胞形是矩曲线
上有限个点的凸包。它具有高度的邻接性:任意至多包含 个顶点的集合都构成一个面。带状多胞形是若干线段的闵可夫斯基和;立方体和许多中心对称多胞形都属于这一族。置换多面体由坐标列表的各个置换构成,而结合多面体的顶点则编码了加括号的方式或多边形的三角剖分;它们将多胞形几何与离散结构联系起来。
极对偶与几何构造
对于内部包含原点的满维多胞体 ,其极多胞体定义为
这里, 表示欧几里得内积。极多胞体同样是内部包含原点的满维多胞体,且 。原点的位置至关重要:平移一个多胞体通常会改变其极多胞体的形状,尽管平移本身并不改变原多胞体的面格。
极对偶会反转关联关系。 的一个非空真 维面对应于 的一个 维面。顶点对应于余维一的面,棱对应于余维二的面,而包含关系的方向则相反。对于上文给出的坐标模型,超立方体的极多胞体是正轴体。更一般地,简单多胞体的极多胞体是单纯多胞体,而单纯多胞体的极多胞体是简单多胞体。面格之间的对偶关系并不要求这两个几何对象全等,甚至不要求它们仿射等价。
有多种构造可以由已有的多胞体生成新的多胞体。笛卡尔积 的维数为 ;多边形与线段的积是棱柱。将 与其仿射包之外的一点取凸包,就得到棱锥,其维数比 高一维。从一个点出发,反复进行棱锥构造可得到单纯形;反复与线段作积则可得到超立方体。双棱锥则是在作为底面的多胞体两侧,以适当的相对位置各放置一个顶点而构成的。
闵可夫斯基和定义为
只要 和 都是多胞体, 就也是多胞体。支撑函数
满足 。这一恒等式说明了支撑超平面在求和运算下的变化规律。带状多胞体恰好是有限条线段的闵可夫斯基和,因此其几何性质与超平面排列密切相关。
仿射映射将多胞体映为多胞体,但可能使其维数降低、面结构退化。多胞体与仿射子空间的截面,只要非空,也仍是多胞体。投影可能使顶点合并、余维一的面消失,而截面则可能在与较高维面的交会处产生新的顶点。这些运算是扩展表述的核心:一个在自身坐标空间中需要许多不等式才能描述的多胞体,可能是某个描述简短得多的高维多胞体的投影。
面数、拓扑与极值界
维多胞形的 -向量为
其中, 表示其 维面的数量。这些数受到很强的约束。最为人熟知的是欧拉关系式:
对于三维多胞形,该式化为 。对于多边形,则得到 。通常将空面的维数规定为 ,并令其数量为 ,这样可以简化更一般的恒等式。
从拓扑角度看,这是因为 维多胞形的边界与球面 同胚。从内部一点出发的径向投影就给出了这样的同胚映射。因此,各维面数的交错和就是其边界的欧拉示性数。多胞形本身则与一个 维闭球同胚。这些事实将有限的面计数问题与拓扑学联系起来,而面分解则提供了可用于计算拓扑不变量的具体胞腔。
对于单纯多胞形,常将各维面数重新组织为 -向量,其定义为
德恩–索默维尔关系式断言,。这些关系式推广了欧拉关系式,揭示了从原始面数中不易直接看出的对称性。-向量还将多胞形组合学与分次代数联系起来:它的各个分量可以表示相关代数对象的分次分量的维数。
上界定理指出,在顶点数固定为 的所有 维多胞形中,循环多胞形在每一维上的面数都达到最大值。彼得·麦克马伦于1970年证明了这一定理。该结果为顶点数固定时边界的复杂程度给出了精确的上界。在适当的假设下,下界定理则刻画了另一端的极值情形;通过反复沿着最大真面粘接单纯形而构造的堆叠单纯多胞形,在其中发挥着核心作用。
对于单纯多胞形,-定理通过对差值 施加条件,完整刻画了可能出现的面向量。这一定理的证明在1980年前后完成:路易斯·比莱拉和卡尔·李证明了充分性,理查德·斯坦利证明了必要性。斯坦利的论证运用了代数几何,揭示出面数之间的不等式可以反映深刻的代数结构。
对于一般的非单纯多胞形,目前还没有同样完整的刻画。普通的面数也未能包含关联面链的信息。旗向量记录了这样的链,能够区分 -向量无法区分的关联模式,从而引出高维情形下更为丰富的计数问题。
体积、格点与算术
满维多胞形的体积是其 维欧几里得测度;对于较低维的多胞形,则在其仿射包中取自然测度。顶点为 的单纯形,其体积为
这一公式将体积与行列式联系起来。一般的多胞形可以三角剖分为内部互不相交的单纯形,从而将体积和积分问题化为有限求和。只使用原有顶点的三角剖分总是存在,不过,允许引入额外的点,可能得到具有不同计算优势的剖分。
闵可夫斯基和的体积具有多项式性质。对于凸多胞形 以及非负实数 ,表达式
是关于 和 的 次齐次多项式。其系数是混合体积,衡量的是形状之间的相互作用,而不仅是各自的大小。在二维情形下,这给出一个包含两个面积及一个混合面积项的二次公式。混合体积将凸几何与不等式以及多项式方程组的解的计数联系起来。
格多胞形的所有顶点都位于 中,这将多胞形理论与数论联系起来。对于格多胞形 ,埃尔哈特多项式用于计算其伸缩像中的整点数:
对于满维格多胞形,这是一个 次多项式,其首项系数等于该多胞形的欧几里得体积,常数项为 。对于单位立方体,
如果顶点坐标是有理数而非整数,那么计数函数一般是拟多项式:其系数随 周期性变化。
埃尔哈特互反律将边界与内部的格点计数联系起来:对于正整数 ,有
在多胞形的仿射包中讨论时,这里的内部应取相对内部。在二维情形下,皮克定理给出一个尤为简洁的恒等式:
其中 和 分别表示内部格点数和边界格点数。
格多胞形也出现在代数几何中。通过标准构造,其整点可以确定单项式以及相关联的射影环面簇。多胞形的法扇记录了沿各个方向,线性泛函在哪些面上取得最大值。当多胞形为有理多胞形时,这一扇提供了代数数据,从而将几何问题转化为有关单项式、锥和分次环的问题。
优化与计算复杂性
有界的线性规划问题是在一个多胞体上求线性泛函的最大值或最小值:
如果可行多胞体非空,则最优解存在,且至少有一个顶点是最优解。更准确地说,所有最优点构成一个面,它可能是单个顶点、一条边,也可能是更高维的区域。这一几何事实解释了为什么即使原问题的变量连续变化,顶点仍然至关重要。
单纯形法在基本可行解之间移动,这通常被解释为沿边从一个顶点移动到另一个顶点。一次换基会改变起作用的约束,并力求改善目标函数值。退化使这一图景变得复杂:多个基可能对应同一个顶点,而一次换基可能只改变基,却不改变所对应的点。尽管单纯形算法在实践中往往十分有效,但对于某些特定的换基规则,存在最坏情况下需要指数时间的例子。列昂尼德·哈奇扬于1979年通过椭球法证明了线性规划可以在多项式时间内求解;纳伦德拉·卡尔马卡于1984年的工作则推动了现代内点法的兴起。
图直径衡量任意两个顶点之间沿边移动所需的最大步数,因此与单纯形类算法有着自然的联系。赫希猜想提出,一个具有 个面的 维多胞体,其图直径至多为 。这里的面指余维为一的面。弗朗西斯科·桑托斯于2010年构造了一个反例。这一猜想被推翻,并不意味着有关换基路径的所有算法问题都已解决:一条短路径未必能在每一步都改善某个特定目标函数的值,而且算法也未必知道如何找到最短路径。
在整数规划中,可行点的坐标被限制为整数。如果可行集有界,这些点的凸包就是另一个多胞体,称为整数包。在整数包上进行线性优化,得到的最优值与原整数规划问题相同,但描述这个整数包所需的不等式,可能远多于最初的松弛问题。割平面法添加对整数解成立的不等式,而分支定界法则将搜索划分为更小的子问题。核心难点往往在于:如何在不完整构造整数包的情况下,掌握其足够多的几何结构。
表示形式的转换和枚举是另外两类计算难题。给定顶点时,可以要求找出所有余维为一的面;给定不等式时,则可以要求找出所有顶点。输出规模本身就可能是指数级的,因此分析复杂性时必须同时考虑输入和输出。精确有理数运算可以验证关联关系,而浮点数实现则需要谨慎处理接近退化的情形,因为几乎重合的超平面或几乎线性相关的坐标可能导致错误的组合判定。
扩展表述提供了另一种策略。算法不直接描述 ,而是描述一个更高维的多面体,其投影为 。所需不等式数量的最小值是衡量扩展复杂性的一个指标。某些具有特定结构的多胞体允许紧凑的扩展表述,而另一些则已被证明,即使引入辅助变量,仍然需要指数数量的不等式。
实现问题与广义多胞体
实现问题研究的是:给定的组合数据能否成为某个凸多胞体的面结构。在二维情形中,任何至少含三个顶点的有限圈都能由凸多边形实现。在三维情形中,施泰尼茨定理将图的实现问题归结为平面性和三顶点连通性。在更高维度中,某些方面的限制宽松得多,另一些方面却复杂得多:组合结构可能满足许多必要条件,却仍然无法由凸多胞体实现。
实现空间记录固定组合类型的所有坐标实现,通常要先进行适当的规范化。这类空间未必是单一而简单的区域。普适性结果表明,四维多胞体的实现空间可以编码极其复杂的代数和拓扑行为。因此,判断一种组合类型能否实现,与求解实数上的多项式方程组和不等式组有关,而不只是把看似合理的局部结构拼接起来。
坐标的算术性质又增添了一层复杂性。有些组合类型允许有理坐标实现,另一些则必然需要无理坐标。因此,存在实数实现,并不保证存在仅使用有理数的实现。保持关联关系的变换或许能简化坐标,但并非总能消除算术上的障碍。因此,可实现性与有理可实现性是两个不同的问题。
定向拟阵抽象提取了向量配置或点配置中描述定向和侧别的符号信息。例如,适当选取的行列式的符号,可以记录哪些有序点集具有正定向、负定向或仿射相关性。这些信息约束了可能出现的面和分离超平面。有些定向拟阵来自实坐标配置,有些则不然;由此形成了一个框架,使人们能够脱离具体的坐标列表来研究几何可实现性。
抽象多胞体用满足关联公理和连通性公理的分次偏序集取代几何实体。其中的元素被解释为面,极大链则称为旗。这些公理刻画了普通多胞体的重要局部性质,包括某些秩差为二的区间中恰好存在两个中间面的要求。抽象多胞体未必是欧几里得空间中凸多胞体的面格,而且无需先找到空间嵌入,就可以研究其自同构群。
非凸多胞体和星形多胞体提供了另一种推广。它们的面可能以凸性所不允许的方式相交,而图示可能无法清楚表明交叉是否算作关联。因此,精确定义必须明确其底层面结构和几何实现。通常称为无限多胞体的无限类比对象进一步拓展了这一领域,但它们不属于凸几何所采用的有限点集凸包定义的范围。
在数学与科学各领域中的应用
多胞形为受约束的概率分布提供了有限模型。具有 种可能结果的概率向量所组成的集合是标准单纯形
它的顶点表示概率全部集中于某一个结果的分布。对概率施加线性约束,会截出更小的多胞形,因此,涉及边际总和或矩条件的可行性问题就转化成了几何问题。线性的期望值在某个顶点处取得最优值,而熵等非线性量则可能在内部取得最优值。
运输多胞形由行和与列和给定的非负矩阵组成。一个尤为重要的例子是由双随机 矩阵组成的伯克霍夫多胞形。伯克霍夫–冯·诺伊曼定理指出,它是置换矩阵的凸包。因此,每个双随机矩阵都可以表示为离散指派的凸组合。这一结果将连续优化与匹配和分配问题联系起来,也展示了多胞形如何通过其顶点来编码有限个组合选择。
许多离散优化问题都采用同样的原理。旅行商多胞形是巡回路线的关联向量的凸包,而匹配多胞形和割多胞形则编码图中选定的边。一条巡回路线可以用零一向量表示,但这些向量的凸包通常具有远比定义初始松弛问题的基本约束丰富得多的不等式结构。多面体分析旨在找出有效不等式、刻画特殊类别的实例,并研究紧凑线性描述的局限。
在数值计算中,多胞形用作计算区域和网格单元。对多边形或多面体区域进行三角剖分,可为有限元法中的分片多项式逼近提供基础。单纯形上的重心坐标提供了局部基函数和插值规则。更一般的多面体网格需要额外的构造,但仍保留了以有限个平面围成的单元来表示复杂区域的优势。求凸包和半空间交也是碰撞检测与几何建模中的基本运算。
在博弈论中,参与者的混合策略位于一个单纯形内。对于有限零和博弈,均衡计算可以表述为一对线性规划,其中的可行多胞形表示概率选择和保底收益。这是一个尤为直观的例子,展示了几何如何将策略条件转化为不等式。
物理学和代数学中也会出现相关结构。有限经典模型中的关联性所组成的凸集可以形成多胞形,其各个面以不等式表达相应的限制。牛顿多胞形记录多项式中非零项的指数向量,保留了与乘法和方程组有关的几何信息。在这些应用中,多胞形不仅仅用于图示问题:它的面结构、投影和算术性质还为相关分析提供了组织框架。
历史发展
最早的系统研究针对的是多边形和三维立体,而非任意维对象。《几何原本》第十三卷构造了五种正凸多面体,并在古典几何框架内确立了它们的分类。阿基米德研究过半正多面体,这些研究通过后世对其工作的记述流传下来。这些探索侧重于长度、角度、作图和对称性,为后来区分几何形状与组合关联关系奠定了基础。
十八世纪,计数的视角带来了决定性的进展。莱昂哈德·欧拉研究了顶点、棱和面之间的关系,给出了如今写作 的凸多面体公式。后续研究明确了这一公式成立的条件,并将其与拓扑学联系起来。1813年,奥古斯丁-路易·柯西证明了他的刚性定理:具有相同组合结构且对应面全等的凸多面体彼此全等。凸性假设至关重要,而这一定理也推动人们将关联关系、局部度量数据和整体形状区分为多面体几何的不同方面。
十九世纪,高维正多胞体开始得到系统研究。路德维希·施莱夫利于十九世纪五十年代建立了它们的分类,其中包括四维中特有的正多胞体。他的工作表明,即使无法借助通常的空间直观来想象,高维类似物依然是具有严密数学结构的对象。后来的论述,尤其是 H. S. M. 考克斯特的工作,通过反射群以及描述面结构和对称结构的系统记号,对正多胞体进行了梳理。
与此同时,另一条发展路线将研究重点从高度对称的例子转向一般凸体与不等式。赫尔曼·闵可夫斯基关于凸几何、支撑函数和数的几何的工作尤其具有影响力,将凸集的形状与算术及线性结构联系起来。恩斯特·施泰尼茨在二十世纪早期的研究,包括他对三维多胞体图的刻画,使组合实现成为一个核心主题,而不再只是绘制立体时的附带问题。
乔治·丹齐格于1947年提出单纯形法,此后线性规划的发展赋予了多胞体理论广泛的计算用途。乔治·B. 丹齐格的优化框架,以及后来关于多面体组合学的研究表明,顶点、维面和投影不仅能够描述古典几何,也能对实际决策问题进行编码。布兰科·格伦鲍姆的《凸多胞体》于1967年首次出版,推动了这一现代领域以几何和组合基础为核心的整合。
后来的发展进一步拓宽了这一学科。关于面数极值的定理将其与交换代数和代数几何联系起来;普适性定理揭示了实现空间的复杂性;优化则引入了高效描述、枢轴规则和扩展复杂度等问题。各个方向都保留了同一个有限几何核心,同时分别借助不同类型的结构:关联关系、度量几何、算术、对称性或计算。