著者

上原 隆平 寺本 幸生

出版者

情報処理学会

雑誌

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