凸多面体とは？
とつためんたい
凸多面体とは、有限個の半空間の共通部分として表せる有界な凸集合のことで、線形計画法や組合せ論の中心的な研究対象です。
凸多面体（convex polytope）とは、有限個の点の凸包として定義される（または有限個の半空間の共通部分として表せる）有界な凸集合のことです。2次元では凸多角形、3次元では正多面体や一般の多面体が典型例となります。
凸多面体には頂点（vertex）・辺（edge）・面（face）という階層的な構造があります。n 次元凸多面体の場合、0 次元（頂点）から (n−1) 次元（ファセット）まで、さまざまな次元の面が存在します。これらの面の個数の間にはオイラーの多面体公式が成立します（3次元では V − E + F = 2）。
凸多面体の重要な性質と応用を挙げると以下のとおりです。
- 線形計画法：実行可能領域が凸多面体になり、最適解は頂点で達成される
- 単体（シンプレックス法の基礎）：n+1 個の頂点を持つ最も基本的な凸多面体
- 組合せ論：f ベクトル・h ベクトルによる面の個数の分析
- 計算幾何学：凸包計算アルゴリズム
正多面体（プラトンの立体）は凸多面体の特殊ケースで古くから研究されてきました。現代では高次元凸多面体の理論が数理計画・最適化・代数的組合せ論・トーリック幾何学など幅広い分野で活躍しています。
使い方・例文
線形計画問題を解くシンプレックス法では、制約条件が定める実行可能領域（凸多面体）の頂点を順にたどることで最適解を探索します。3次元の場合は立方体や三角柱などが制約領域として現れます。
この用語をシェア
最終更新: