折り紙を中心とした剛体グラフ構造の複雑さの研究

点击翻译按钮获取中文摘要

本研究テーマでは、折り紙に代表される「長さ」や「面積」などの属性を持つ素材を「物理的な構造をもっグラフ」としてモデル化し、コンピュータサイエンスの対象として研究を行った。そしてそのグラフ上の問題の複雑さを解析したり、効率のよいアルゴリズムを開発することを目的とした。そして平成22年度は以下の研究成果を得た。1. Crease widthの提案と解析:紙を折ったとき、折り目に挟まる紙は少ないほどよい。この直観を問題として定式化し、crease widthという概念を提案した。そして数え上げの観点からcrease widthを研究し、与えられた折り目に矛盾しない折り方の個数に関する上界と下界を得た。2. 展開図の研究:正多面体同士の間の共通の展開図を研究した。その結果、(1)辺による展開ではこうした展開図は得られないこと(2)多少の歪みを認めるなら、いくつかの多面体間の共通の展開図が作れること(3)極限として正四面体と立方体がどちらも折れる展開図が存在することなどを示した。3. 折り紙における非決定性問題:折り紙の現実的なモデルにおいて、非常に基本的な問題が計算機では判定不能であることを証明した。また、もう少し抽象的な構造を持ったグラフに関する理論的な研究成果もいくつか得ることができた。これらは適宜国際会議や論文誌に発表し「EATCS/LA Best Presentation Award」という賞も受賞した。挑戦的萌芽研究として十分な成果をあげることができた。