凸多面体

グリュンバウムは著書『凸多面体』の中で、凸多面体を有限個の極点を持つコンパクトな凸集合と定義している。

セット${\displaystyle K}$の$\displaystyle \mathbb {R} ^{n}}$凸であるのは、異なる点のペアごとに、${\displaystyle a}$、${\displaystyle b}$で${\displaystyle K}$、終点を持つ閉じたセグメント${\displaystyle a}$そして${\displaystyle b}$中に含まれる${\displaystyle K}$。

これは、有限個の点の凸包として有界凸多面体を定義することと同等であり、その有限個の点の集合には多面体の極点の集合が含まれていなければなりません。このような定義は頂点表現（V表現またはV記述）と呼ばれます。^{[ 1 ]}コンパクトな凸多面体の場合、最小のV記述は一意であり、多面体の頂点 の集合によって与えられます。 ^{[ 1 ]}凸多面体は、そのすべての頂点が整数座標を持つ場合、整数多面体と呼ばれます。

凸多面体は、有限個の半空間の交差として定義できます。このような定義は、半空間表現（H表現またはH記述）と呼ばれます。^{[ 1 ]}凸多面体のH記述は無限に存在します。しかし、完全な次元の凸多面体の場合、最小のH記述は実際には一意であり、ファセットを定義する半空間 の集合によって与えられます。^{[ 1 ]}

閉じた半空間は線形不等式として表すことができる：^{[ 1 ]}

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b}$

どこ${\displaystyle n}$は、検討対象の多面体を含む空間の次元である。したがって、閉じた凸多面体は、線形不等式系の解の集合とみなすことができる。

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&b_{m}\\\end{alignedat}}}$

どこ${\displaystyle m}$は、多面体を定義する半空間の数です。これは、行列不等式として簡潔に記述できます。

${\displaystyle Ax\leq b}$

どこ${\displaystyle A}$は${\displaystyle m\times n}$マトリックス、${\displaystyle x}$は${\displaystyle n\times 1}$座標が変数である列ベクトル${\displaystyle x_{1}}$に${\displaystyle x_{n}}$、 そして${\displaystyle b}$は${\displaystyle m\times 1}$座標が右辺である列ベクトル${\displaystyle b_{1}}$に${\displaystyle b_{m}}$スカラー不等式の。

開凸多面体も同様に定義されるが、式の中では非厳密な不等式の代わりに厳密な不等式が用いられる。

各行の係数${\displaystyle A}$そして${\displaystyle b}$それぞれの半空間を定義する線形不等式の係数に対応します。したがって、行列の各行は、多面体を支える超平面、つまり多面体を含む半空間を境界付ける超平面に対応します。支える超平面が多面体と交差する場合、それは境界超平面と呼ばれます（支える超平面であるため、多面体の境界でのみ多面体と交差します）。

上記の定義は、多面体が完全な次元であることを前提としています。この場合、定義不等式（正の数による乗算を除く）の最小集合が一意に存在します。この最小集合に属する不等式は、本質的不等式と呼ばれます。本質的不等式を等号で満たす多面体の点の集合は、ファセットと呼ばれます。

多面体が完全な次元でない場合、${\displaystyle Ax\leq b}$の適切なアフィン部分空間に位置する$\displaystyle \mathbb {R} ^{n}}$そして、この部分空間における対象として多面体を研究することができる。この場合、多面体のすべての点が満たす線形方程式が存在する。これらの方程式のいずれかを定義不等式に追加しても、多面体は変化しない。したがって、一般に、多面体を定義する一意の最小不等式集合は存在しない。

一般に、任意の半空間の交わりは必ずしも境界を持つ必要はない。しかし、凸包と同等の定義を求める場合は、境界を明示的に要求する必要がある。

これら2つの表現を組み合わせることで、与えられたベクトルが与えられた凸多面体に含まれるかどうかを効率的に判定できる。ベクトルが多面体に含まれることを示すには、それを多面体の頂点の凸結合として表現すれば十分である（V記述が用いられる）。ベクトルが多面体を含まないことを示すには、ベクトルが破る単一の定義不等式を示せば十分である。^{[ 5 ]： 256}

ベクトルによる表現における微妙な点は、ベクトルの数が次元に対して指数関数的に増加する可能性があるため、ベクトルが多面体に含まれることの証明が指数関数的に長くなる可能性があることです。幸いなことに、カラテオドリの定理により、多面体内のすべてのベクトルは、空間の次元をdとしたとき、最大でd + 1 個の定義ベクトルで表現できることが保証されています。

非有界多面体（多面体とも呼ばれる）の場合、H 記述は依然として有効ですが、V 記述を拡張する必要があります。テオドール・モツキン(1936) は、任意の非有界多面体は、有界多面体と凸多面体円錐の和として表すことができることを証明しました。^{[ 6 ]}言い換えれば、非有界多面体内のすべてのベクトルは、その頂点 (定義点) の凸和と、その無限辺 (定義線) のユークリッドベクトルの円錐和の合計です。これは有限基底定理と呼ばれます。^{[ 3 ]}

凸多面体の面とは、多面体の内部点がいずれも半空間の境界上にないような、多面体と半空間との任意の交点のことである。言い換えれば、面とは、多面体の有効な不等式において等号を与える点の集合である。^{[ 5 ]： 258}

多面体がd次元である場合、そのファセットは ( d − 1) 次元の面であり、頂点は0 次元の面であり、辺は1 次元の面であり、稜線は( d − 2) 次元の面である。    

行列不等式で定義される凸多面体Pが与えられた場合${\displaystyle Ax\leq b}$Aの各行が境界超平面に対応し、他の行と線形独立である場合、等号が成り立つ限り、 Pの各面はAのちょうど 1 つの行に対応し、その逆も同様です。特定の面上の各点は、行列の対応する行の線形等号を満たします。（他の行の等号も満たす場合と満たさない場合があります）。同様に、リッジ上の各点は、Aの 2 つの行の等号を満たします。

一般に、( n − j )次元面は、Aのj個の特定の行において等号を満たします。これらの行は面の基底を形成します。幾何学的に言えば、これは、面が多面体の境界超平面のj個の交点にある多面体上の点の集合であることを意味します。  

凸多面体の面は、面格子と呼ばれるオイラー格子を形成し、その面格子では、面の集合包含関係によって部分順序が決定されます。上記の面の定義により、多面体自体と空集合の両方を面とみなすことができ、面格子においてすべての面のペアが結合点と交わり点を持つことが保証されます。多面体全体は格子の唯一の最大要素であり、すべての多面体の（-1）次元面（ヌル多面体）とみなされる空集合は、格子の唯一の最小要素です。

2つの多面体は、それらの面格子が同型である場合に、組み合わせ論的に同型であると呼ばれる。

多面体グラフ（多面体グラフ、エッジグラフ、多面体のグラフ、または1-スケルトンとも呼ばれる）は、高次元の面を無視して、多面体の頂点とエッジのみの集合です。たとえば、多面体グラフは、 3 次元多面体の多面体グラフです。Whitney ^{[ 7 ]}の結果により、 3 次元多面体の面格子は、そのグラフによって決定されます。任意の次元の単純多面体 についても同様です(Blind & Mani-Levitska 1987、 Micha Perlesの予想を証明)。^{[ 8 ]} Kalai (1988) ^{[ 9 ]}は、一意のシンク方向に基づく簡単な証明を与えています。これらの多面体の面格子はグラフによって決定されるため、2 つの 3 次元または単純な凸多面体が組み合わせ的に同型であるかどうかを判定する問題は、グラフ同型問題の特殊なケースとして等価に定式化できます。ただし、これらの問題を逆方向に翻訳することも可能であり、多面体同型性テストがグラフ同型性完全であることを示すことができます。^{[ 10 ]}

凸多面体は、R ⁿの任意のコンパクトな凸部分集合と同様に、閉球と同相です。^{[ 11 ]}多面体の次元をmとします。多面体が全次元の場合、m = nとなります。したがって、凸多面体は境界を持つm次元多様体であり、そのオイラー標数は1 であり、基本群は自明です。凸多面体の境界は( m − 1) 次元球面と同相です。境界のオイラー標数は、mが偶数の場合は 0、 mが奇数の場合は 2 です。境界は、( m − 1) 次元球面空間のテセレーション、つまり球面タイリングとみなすこともできます。    

凸多面体は、特定の性質を満たす単体複体、すなわち単体の和集合に分解することができる。

凸なr次元多面体Pが与えられたとき、 ( r +1)個のアフィン独立点を含む頂点の部分集合はr単体を定義します。対応する単体の和集合がPに等しく、任意の 2 つの単体の共通部分が空集合またはより低次元の単体となるような部分集合の集合を形成することが可能です。単体の体積は簡単に式で与えられるため、この単体分解は凸多面体の体積を計算する多くの方法の基礎となっています。^{[ 12 ]}

すべての正凸多面体（プラトン立体）は、その特徴的な直交図の偶数個のインスタンスに分割することができる。

凸多面体の異なる表現はそれぞれ異なる有用性を持つため、ある表現が与えられた場合に別の表現を構築することは重要な問題である。V表現の構築問題は頂点列挙問題として知られ、H表現の構築問題は面列挙問題として知られている。有界凸多面体の頂点集合はそれを一意に定義するが、様々な応用において、多面体の組み合わせ構造、すなわち面格子についてより詳しく知ることが重要となる。様々な凸包アルゴリズムは、面列挙と面格子構築の両方を扱う。

平面の場合、すなわち凸多角形の場合、ファセット列挙問題と頂点列挙問題はどちらも、凸包の周りの頂点（または辺）を順序付けることに相当します。凸多角形が多角形の従来の方法、つまり頂点の順序付きシーケンスによって指定されている場合、これは自明な作業です。${\displaystyle v_{1},\dots ,v_{m}}$入力された頂点（または辺）のリストが順不同の場合、問題の時間計算量はO ( m  log m ) になります。^{[ 13 ]}代数的決定木モデルの計算では、対応する下限が知られています。^{[ 14 ]} 

凸多面体の体積を計算するタスクは、計算幾何学の分野で研究されてきました。メンバーシップオラクルにアクセスできる場合、例えば凸体積近似法を使用して、体積を近似的に計算できます。正確な計算に関しては、凸多面体を線形不等式の方程式系として表現した場合、多面体の体積のビット長がこの表現で多項式にならないという障害があります。^{[ 15 ]}