著者

上原 隆平 寺本 幸生

出版者

情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.71, pp.59-64, 2006-07-03

---

折り紙は伝統的な紙工芸であるが,近年,科学としての認知が高まり,数学的な研究が進められている.本論文ではもう一つの伝統的な紙工芸である,飛び出す絵本を取り上げる.飛び出す絵本をデザインする問題を定式化し,その複雑さを議論する.そして本を閉じる問題も,本を開く問題も,ともにNP困難であることを示す.Origami is the centuries-old art of folding paper, and recently, it is investigated as science. In this paper, another hundreds-old art of folding paper, a pop-up book, is studied. A model for the pop-up book design problem is given,and its complexity is investigated. We show that both of the opening book problem and the closing book problem are NP-hard.

著者

岡本 吉央 上原 隆平

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1649, pp.58-65, 2009-05

著者

Demaine Erik D. Demaine Martin L. 上原 隆平 宇野 毅明 宇野 裕之

出版者

京都大学

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.1744, pp.48-55, 2011-06

著者

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

出版者

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

雑誌

研究報告アルゴリズム(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.

著者

上原 隆平

雑誌

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

巻号頁・発行日

vol.2010-AL-131, no.11, pp.1-3, 2010-09-15

---

近年,計算幾何学の一部で 「計算折紙」 とよばれる分野が注目を集めている.その分野では,ある意味で折紙を計算のプラットフォームとみなしている.こうしたプラットフォーム上で,計算量理論的に手におえない困難な問題や,多項式時間で解ける問題がいくつか知られている.さてチューリング機械といった標準的な計算モデルにとって,決定不能な問題の存在は,その計算モデルの計算能力の高さを逆説的に示しているといえよう.それならば,計算折紙モデルでは決定不能な問題が存在するだろうか?本稿では,この疑問に対する解答を与える.具体的には,計算折紙モデルのごく自然な決定問題が決定不能であることを示す.