じゃばら折りの複雑さに関する研究
スポンサーリンク
概要
- 論文の詳細を見る
本稿では「じゃばら折り」に関する新しい折り紙の問題を提案する.本問題では与えられた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
著者
-
上原 隆平
北陸先端科学技術大学院大学
-
今堀 慎治
東京大学大学院情報理工学系研究科
-
上原 隆平
北陸先端科学技術大学院大学情報科学研究科
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
上原 降平
北陸先端科学技術大学院大学情報科学研究科
-
伊藤 剛志
School of Computer Science, McGill University
-
清見 礼
北陸先端科学技術大学院大学情報科学研究科
-
伊藤 剛志
School Of Computer Science Mcgill University
-
上原 隆平
北陸先端科学技術大学院大学 情報科学研究科
-
清見 礼
北陸先端科学技術大学情報科学研究科
-
清見 礼
北陸先端科学技術大学院大学
関連論文
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- Bipartite Permutation Graphのランダム生成と列挙
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- ハイブリッドメタ戦略(OR事典Wiki)
- 再構成問題の計算複雑さ
- あみだくじの高速列挙
- 折紙の計算量的複雑さの研究 (小特集 折紙工学の現状と課題)
- 折紙の計算量的複雑さの研究(折紙工学の現状と課題)
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)