風船をねじって多面体を作る「計算風船ひねり」の理論

Computational Balloon Twisting: The Theory of Balloon Polyhedra [pdf]

本論文は、風船動物や風船多面体などの風船ひねり構造を、そのグラフ（辺骨格）としてモデル化し、数学的・アルゴリズム的な理論を構築する。具体的には、与えられたグラフを正確に作るための最小本数の風船を見つけるアルゴリズムや、より少ない本数で繰り返しや近道を許す場合の最小総長さを求めるアルゴリズムを提供する。一方で、等しい長さの風船で最適な構造が可能かどうかを判定する問題がNP完全であることを示す。さらに、プラトン立体やアルキメデス立体に対する最適な風船多面体の構成も与える。