じゃばら折りの複雑さに関する研究

概要

論文の詳細を見る
本稿では「じゃばら折り」に関する新しい折り紙の問題を提案する.本問題では与えられたn個の山折り/谷折りの割り当てに対して,紙をその割り当てに従って等間隔に折ることを目的とする.扱う紙のモデルは以下の通り.(1)紙は厚み0で重ねて一度に複数枚折ることができる.(2)それぞれの折り状態は平坦である.(3)それぞれの折り目はそこで最後に折られたときの折り状態を記憶する.(4)紙はn箇所の折り目を除いて剛体である.このモデルにおいて,与えられた割り当てを実現する効率の良い折り操作を見つけることがこの問題の目的である.一般の山谷割り当てに対する問題を単位長折り問題と呼び,山谷割り当てが「MV MV MV…」という形をしているときは特にじゃばら折り問題と呼ぶことにする.アルゴリズムの複雑さは折りの回数によって測り,折りを開く回数は無視する.この問題には自明な上界nと自明な下界log(n+1)が存在する.本稿ではまず以下の非自明な2つの上界を示す.(a)どんな山谷割り当てでも高々「n/2」+「log(n+1)」回の折りで実現することができる.(b)任意のε>0に対してじゃばら折りはO(N^ε)回の折りで実現することができる.次に以下の非自明な下界を示す.(c)ほとんどすべての山谷割り当てはΩ(n/(log n))回折らなければ作ることができない.結果(b)と(c)より,じゃばら折り問題は単位長折り問題の中では簡単な部類に入ることがわかった.
社団法人情報処理学会の論文
2009-01-23

じゃばら折りの複雑さに関する研究

スポンサーリンク

概要

著者

関連論文

スポンサーリンク