頂点列挙問題

数学において、多面体、多面体セル複合体、超平面配置、またはその他の離散幾何学的オブジェクトの頂点列挙問題とは、オブジェクトの形式的な表現が与えられた場合にオブジェクトの頂点を決定する問題である。古典的な例としては、一連の線形不等式によって指定される凸多面体の頂点を列挙する問題が挙げられる。^[1]

${\displaystyle Ax\leq b}$

ここで、Aはm × n行列、xは変数のn × 1 列ベクトル、b は定数のm × 1 列ベクトルです。頂点が与えられた場合に境界不等式を見つける逆 (双対) 問題は、ファセット列挙と呼ばれます(凸包アルゴリズムを参照)。

この問題の計算の複雑さはコンピュータサイエンスの研究対象である。無限多面体の場合、この問題はNP困難であることが知られており、より正確には、P=NPでない限り、入力と出力を組み合わせたサイズで多項式時間で実行されるアルゴリズムは存在しない。^[2]

1992 年のDavid AvisとKomei Fukuda ^[3]による論文では、 d次元のn個の不等式の非退化システムによって定義される多面体の v 頂点(または、d 次元の n 点の凸包の v 面。ここで、各面には正確に d 個の点が含まれます) を時間 O(ndv) と空間 O(nd) で見つける逆探索アルゴリズムが紹介されています。d 次元の n 個の超平面の単純な配置内のv 頂点は、O(n2dv) の時間と O(nd) の空間計算量で見つけることができます。Avis – Fukudaアルゴリズムは、方向付けられたマトロイドのcriss - ^crossアルゴリズムを適応させたものです。

• Avis, David ; Fukuda, Komei (1992 年 12 月)。「凸包のピボット アルゴリズムと、配置と多面体の頂点列挙」。離散および計算幾何学。8 ( 1): 295–313。doi : 10.1007/ BF02293050。MR  1174359 。