著者

伊藤 剛志 清見 礼 今堀 慎治 上原 隆平

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.9, pp.1-8, 2009-01-23

---

本稿では 「じゃばら折り」 に関する新しい折り紙の問題を提案する.本問題では与えられた n 個の山折り/谷折りの割り当てに対して,紙をその割り当てに従って等間隔に折ることを目的とする.扱う紙のモデルは以下の通り. (1) 紙は厚み 0 で重ねて一度に複数枚折ることができる. (2) それぞれの折り状態は平坦である. (3) それぞれの折り目はそこで最後に折られたときの折り状態を記憶する. (4) 紙は n 箇所の折り目を除いて剛体である.このモデルにおいて,与えられた割り当てを実現する効率の良い折り操作を見つけることがこの問題の目的である.一般の山谷割り当てに対する問題を単位長折り問題と呼び,山谷割り当てが 「MV MV MV ...」という形をしているときは特にじゃばら折り問題と呼ぶことにする.アルゴリズムの複雑さは折りの回数によって測り,折りを開く回数は無視する.この問題には自明な上界、と自明な下界 log (n + 1) が存在する.本稿ではまず以下の非自明な 2 つの上界を示す. (a) どんな山谷割り当てでも高々 [n/2] + [log (n+1)] 1 回の折りで実現することができる. (b) 任意の ∊>0 に対してじゃばら折りは 0 (n∊) 回の折りで実現することができる.次に以下の非自明な下界を示す. (c) ほとんどすべての山谷割り当ては Ω (n/log n) 回折らなければ作ることができない結果 (b) と (c) より,じゃばら折り問題は単位長折り問題の中では簡単な部類に入ることがわかった.We introduce a new origami problem about pleats foldings. For a given assignment of n creases of mountains and valleys, we make a strip of paper well-creased according to the assignment at regular intervals. We assume that (1) paper has 0 thickness and some layers beneath a crease can be folded simultaneously, (2) each folded state is flat, (3) each crease remembers its last folded state made at the crease, and (4) the paper is rigid except at the n given creases. On this model, we aim to find efficient ways of folding a given mountain-valley assignment. We call this problem unit folding problem for general patterns, and pleats folding problem when the mountain-valley assignment is "MVMVMV…" The complexity is measured by the number of foldings and the cost of unfoldings is ignored. Trivially, we have an upper bound n and a lower bound log [(n+1).] We first give some nontrivial upper bounds: (a) any mountain-valley assignment can be made by [n / 2 ] + [log (n+1) ] foldings, and (b) a pleats folding can be made by O (n∊) foldings for any ∊>0. Next, we also give a nontrivial lower bound: (c) almost all mountain-valley assignments require Ω(log n / n) foldings. The results (b) and (c) imply that a pleats folding is easy in the unit folding problem.