N次元多面体

n次元多面体は、3 次元多面体をn次元空間に一般化した幾何学的オブジェクトです。任意の次元nの実アフィン(またはユークリッド) 空間内の平面を持つ点の集合として定義されます。また、有限個の半空間の交差として定義することもできます。3 次元多面体とは異なり、境界付きまたは境界なしの場合があります。この用語では、境界付き多面体は多面体と呼ばれます。^{[1] [2]}

解析的には、凸多面体は線形不等式a _i ^T x ≤ bi_の解集合として表現されます。ここで、a _iはR ⁿのベクトル、b _iはスカラーです。この多面体の定義は、線形計画法の問題に幾何学的な視点を提供するため、特に重要です。^{[3] : 9}

多くの伝統的な多面体形式は n 次元多面体です。その他の例としては、次のものがあります。

• 半空間は、単一の線形不等式a ₁ ^T x ≤ b ₁によって定義される多面体です。
• 超平面は、2 つの不等式、 a ₁ ^T x ≤ b ₁とa ₁ ^T x ≥ b ₁ ( -a ₁ ^T x ≤ - b ₁に相当) によって定義される多面体です。
• 平面上の象限。たとえば、水平軸の上と垂直軸の右側にあるすべての点で構成されるデカルト平面の領域: { ( x , y ) : x ≥ 0, y ≥ 0 }。その辺は 2 つの正の軸であり、それ以外は境界がありません。
• ユークリッド 3 次元空間の八分円、 {( x、y、z ): x ≥ 0、y ≥ 0、z ≥ 0 }。
• 無限の広がりを持つプリズム。たとえば、3 次元空間の二重無限正方形プリズムは、z軸に沿ってスイープされたxy平面の正方形で構成されます: { ( x、y、z ) : 0 ≤ x ≤ 1、 0 ≤ y ≤ 1 }。
• ボロノイ分割の各セルは多面体です。集合Sのボロノイ分割では、点c ∈ Sに対応するセルA は、 c がSの凸包の内部にある場合は有界（つまり従来の多面体）であり、それ以外の場合（c がSの凸包の境界上にある場合）はAは無界です。

多面体Pの部分集合Fは、半空間H（不等式a ₁ ^T x ≤ b ₁で定義される）が存在し、 HがPを含み、FがHとPの交差であるとき、 Pの面と呼ばれる。^{[3] ：9}

• 面に単一の点 { v } が含まれる場合、v はPの頂点と呼ばれます。
• 面Fが空でなく、n -1 次元である場合、F はPの面と呼ばれます。

P がAx ≤ bで定義される多面体であり、Aが完全な列ランクを持つと仮定する。このとき、v がPの頂点であるための必要条件は、v が線形システムAx ≤ bの基本実行可能解である場合である。^{[3] : 10}

多面体を線型不等式の集合で表現することは一意ではない。各多面体Pに対して標準的な表現を定義するのが一般的である: ^{[3] :9}

• Pがフル次元の場合、その標準的な表現は不等式の集合であり、各不等式a _i ^T x ≤ b _{i は}Pのちょうど 1 つの面を定義し、さらに不等式はすべてのiに対してとなるように正規化されます。${\displaystyle \|a_{i}\|_{\infty }=1}$
• Pがフル次元でない場合、 P は、線形方程式C x= dのセットによって定義されるアフィン包に含まれます。 C = ( I、C ' )となるようにC を選択できます。ここで、 I は単位行列です。 Pの標準表現には、このセットC x= dと、各不等式 a i _T ^x ≤ b i_がPのちょうど 1 つの面を定義するような不等式のセットが含まれます。不等式は、すべてのiに対して、各a _{i が}Cの各行に直交するように正規化されます。この表現は、単位行列の列の選択まで一意です。${\displaystyle \|a_{i}\|_{\infty }=1}$

P が多面体（有界多面体）である場合、 P は単にVの凸包であるため、頂点の集合Vによって表すことができます：P = conv( V )。

P が一般的な（おそらく無限の）多面体である場合、それは次のように表すことができます： P = conv(V) + cone(E)、ここでVは（前述と同様に） Pの頂点の集合、Eは別の有限集合、 cone は円錐包を表します。集合 cone(E) はPの後退円錐とも呼ばれます。^{[3] ： 10}

カラテオドリの定理は、Pがd次元多面体である場合、 P内のすべての点は、最大でd +1個のアフィン独立頂点の凸結合として表すことができる、と述べています。 この定理は一般化することができ、P が任意のd次元多面体である場合、 P内のすべての点は、 s + t ≤ d +1である点v ₁、...、v _s、v ₁ + e ₁、...、v ₁ + e _tの凸結合として表すことができます。ここで、 v ₁、...、v _{s は}Pの最小の空でない面の要素であり、e ₁、...、e _tはP の後退円錐の最小の非ゼロ面の要素です。^{[3] : 10}

多面体に関するアルゴリズム問題を解く場合、ある多面体が少数のビット数で表現できるかどうかを知ることが重要である。多面体の表現の複雑さにはいくつかの尺度があるP : ^{[3] :163}

• P が有理係数を持つ線形不等式のシステムで表すことができ、各不等式のエンコード長（つまり、不等式の係数として現れるすべての有理数のバイナリエンコード長）が最大でf である場合、P のファセット複雑度は最大で fです。各不等式には n+1 個の係数があるため、 f ≥ n +1 であることに注意してください。
• P がconv( V )+cone( E )として表せる場合、 Pの頂点複雑度は最大でvになります。ここで、 VとE は有限集合であり、 V または E 内の各点のエンコード長は最大でvです。各ベクトルにはn個の係数があるため、v ≥ n であることに注意してください。

これら2種類の複雑さは密接に関連している：^{[3] ：Lem.6.2.4}

• P の面複雑度が最大でfである場合、 P の頂点複雑度は最大で 4 n ² fになります。
• P の頂点複雑度が最大でvである場合、 P の面複雑度は最大で 3 n ² vになります。

多面体P は、 n (次元数) とf (面の複雑さの上限)がわかっている場合に、適切に記述されているとされます。これは、 nとv (頂点の複雑さの上限) がわかっていることを要求するのと同じです。

多面体Pの面の複雑さの上限はわかっているが、その上限に達する特定の不等式はわかっていない場合がある。しかし、Pの任意の標準表現における符号化長は最大で 35 n ² fであることが証明されている。^{[3] : Lem.6.2.3}

Pの表現の複雑さはPの体積の上限と下限を意味する：^{[3] ：165}

• P の頂点複雑度が最大でもvであれば、自明に、Pのすべての頂点は原点の周りの半径 2 ^vの球に含まれます。つまり、Pが多面体であれば、 P 自体はその球に内接します。
• P が、面の複雑さが最大でfであるフル次元多面体である場合、Pには半径 の球が含まれます。 さらに、この球は原点の周りの半径 の球に含まれます。${\displaystyle 2^{-7n^{3}f}}$${\displaystyle 2^{5n^{2}f}}$

表現の複雑さが小さいと、近似解を正確な解に「丸める」のに役立ちます。具体的には、^{[3] ：166}

• Pが面の複雑さが最大でf の多面体であり、yが共通分母が最大でqである有理ベクトルであり、 yからPまでの距離が最大で 2 ^{-2 f} / qである場合、y は実際にPに含まれます。
• P が頂点複雑度が最大でv の多面体であり、不等式a ^T x ≤ b + 2 ^-v-1を満たす場合、Pは不等式a ^T x ≤ b も満たします。
• Pが面の複雑さが最大でfである多面体であり、v がPからの距離が最大で 2 ^{-6n f}である有理ベクトルであり、qとw がを満たす整数ベクトルである場合、点w / qはPに含まれます。数qとベクトルw は、同時ディオファントス近似を使用して多時間で見つけることができます。${\displaystyle \|qv-w\|<2^{-3f},0<q<2^{4nf}}$
• P が頂点複雑度が最大でv の多面体であり、不等式a ^T x ≤ b + 2 ^-6nvを満たし、 q、c、d が を満たす整数ベクトルである場合、Pは不等式 c ^T x ≤ d を満たします。数q、dおよびベクトルc は、同時ディオファントス近似を使用して多時間で見つけることができます。${\displaystyle \|qa-c\|+|qb-d|<2^{-3v},0<q<2^{4nv}}$

• 凸集合上のアルゴリズム問題