多面体の数え上げ

摘要

点の個数がn個であり，面の個数がf個であるような，異なる3次元多面体の個数を求めることは，幾何学における有名な未解決問題の一つである．また多面体の効率的な数え上げアルゴリズムもこれまで知られていなかった．最近，底辺付き極大平面的グラフを，効率良く列挙するアルゴリズムが，我々によって設計された．本論文では，このアルゴリズムをもとにして，すべての面が三角形であるような多面体の効率的な数え上げアルゴリズムを設計する．また，このアルゴリズムを実装し，4 ≤ n ≤ 15なる各nについて，点の個数がnでありすべての面が三角形であるような多面体の個数を数え上げたので報告する．また列挙したグラフのすべてをWWW上で公開したので報告する．