Complexity of pleat folding (Theoretical Computer Science and Its Applications)
Tsuyoshi Ito, Masashi Kiyomi, Shinji Imahori, Ryuhei Uehara · Institutional Repositories DataBase (IRDB) · 2009
We introduce a new origami problem about pleat foldings.For a given assign- ment of $n$ creases of mountains and val- leys, we make a strip of paper well-creased according to the assignment at regular in- tervals.We use simple folding as a ba- sic operation.More precisely, we assume that (1) paper has $0$ thickness and some layers beneath a crease can be folded simultaneously, (2) each folded state is flat, and (3) the paper is rigid except at the $n$ given creases.We also assume that each crease remembers its last folded state made at the crease.Wc aim to find ef- ficient ways of folding a given mountainvalley assignment in this model.We call this problem unit folding problem for general patterns, and pleat folding problem when the mountain-valley assignment is MVMVMV $\cdots.$"The complexity is measured by the number of foldings and the cost of unfoldings is ignored.Tlrivially, we have an upper bound $n$ and a lower bound $\log(n+1)$ .We first give some non-$