Computational Origami
Ryuhei Uehara
Japan Advanced Institute of Science and Technology (JAIST)
School of Information Scienceuehara@jaist.ac.jp
http://www.jaist.ac.jp/~uehara
2020/01/29

I628E: Information Processing Theory

Today’s Topic
5. Time Complexity• “Folding complexity”•

Theoretically, the world fastest algorithm for pleat folding••

Recursive analysis and Fibonacci sequenceLower bound by counting method• We can use some techniques in TCS.

6. Space Complexity (?)• Stamp Folding Problem• Minimization of Crease width•

NP-complete problem, FPT algorithm

7. Undecidable Origami Problem• Diagonalization and undecidability

2020/01/29

I628E: Information Processing Theory

Stamp Folding Problem
Reference:
Ryuhei Uehara, Stamp foldings with a given mountain-valley
assignment in ORIGAMI5, pp. 585-597, CRC Press, 2011.

2020/01/29

I628E: Information Processing Theory• Pleat folding is…
• Alternating foldings ofMountain and Valley• Basic tool of Origami• Many applications
Extension to General
Patterns and consider its
complexity…

Quite
important!!
Tokyo Monorail

JAIST Bus• Complexity of folding(?)• From the viewpoint of Computer Science• Two resources of a computation model;
1. time2. space

Crease width of a paper＝
the number of papers between two hinged papers• Two resources of Origami model?

1. time…the number of foldings (operations)•J. Cardinal, E. D. Demaine, M. L. Demaine, S. Imahori, T. Ito, M. Kiyomi,
S. Langerman, R. Uehara, and T. Uno: Algorithmic Folding Complexity,Graphs and Combinatorics, accepted, 2010.

2. space…???

It is better to have less stretch
at each crease point• 2020/01/29 • I628E: Information Processing Theory

New problem
Crease width minimization problem

Input: Paper of length n+1 and s∈{M, V}n
Output: folded paper according to s
Goal: Find a good folded state with small crease width• At each crease, the number of papers between
the papers hinged at the crease is crease width.
• Two minimization problems;• minimize maximum• minimize total (=average)No!!

It seems simple,… so easy??
2020/01/29
I628E: Information Processing Theory

New problem•

Simple non-trivial example

Input: MMVMMVMVVVV

The number of feasible folded states：100
Goal: Find a good folded state with small crease width•

The unique solution having min. max. value 3[5|4|3|6|7|1|2|8|10|12|11|9]

total=13•

2020/01/29

The unique solution having min. total value 11[5|4|3|1|2|6|7|8|10|12|11|9]

I628E: Information Processing Theory

Max=4

New problem•

Minimization problem for crease width

Input: Paper of length n+1 and s∈{M, V}n
Output: folded paper according to s
Goal: Find a good folded state with small crease width• Two minimization problems; max/total(average)• A few facts;•••a pattern has a unique folded state iff it is pleats
solutions of {min max} and {min total} are different
depending on a crease pattern.
there is a pattern having exponential combinations

MV MV MV MV MV

2020/01/29

V MV MV MV MV M

I628E: Information Processing Theory

Minimization of crease width• Open problem： (Solved later…)•Tractable/Intractable?

• NP-hard?
• Poly-time solvable by Dynamic Programming?
It is NP-hard in general for min-max, and still open for total.
If total is k, we find a fixed parameter tractable algorithmfor k.
• Then, exhaust search technique, that produces all
possible folding ways, works?
average?

exponentialpattern

2020/01/29

pleatsNo!!

I628E: Information Processing Theory

Average case…
The number of folding ways for a random pattern••

Θ(1.65n) by experimentsΩ(1.53n) and O(2n) by theoretical lower/upperbounds… so a naïve program runs veeeerrrrrry slow.

This problem is known as a stamp folding problem,
which is a classic open problem, and I accidentally
improved the lower bound 
2020/01/29

I628E: Information Processing Theory

Stamp folding problem

Average number of folding ways for a random pattern= f(n)/2n, wheref(n) = # of folding ways (or folded states) of a paper of length n+1(summation for all possible patterns)

I give some bounds of f(n):“The On-Line Encyclopedia of Integer Sequences” tells us up ton=28 (by enumeration);f(n)～Θ(3.3n).
You should
I have upper/lower bounds;
know
upper bound: f(n)=O(4n)OEISnlower bound: f(n)=Ω(3.07 )2020/01/29

I628E: Information Processing Theory

Stamp folding problem
The upper bound O(4n) comes from the Catalan number.
[Proof]If the paper of length n+1 is folded,
the crease points should be nested.
No way!!
NestNest

2020/01/29（（）（））（（）（（）））

･（（）（）（））（（･））Combination of n/2 pairsof ()＝
Catalan Number Cn/2
×Combination of n/2 pairsof ()＝
Catalan Number Cn/2

I628E: Information Processing Theory

Stamp Folding Problem

Lower bound[Theorem] Its lower bound is Ω(3.07n).

[Proof] We consider “folding of the last k+1 unit papers”;
k+1

We let• f(n): the number of folding ways of length n+1• g(k): the number of folding ways of length k+1 s.t.
the leftmost endpoint is not coverednThen, we have1/( k −1) n
k −1f (n) ≥ ( g (k )) =g (k )(2020/01/29

I628E: Information Processing Theory)

Stamp Folding Problem• Lower bound[Theorem] Its lower bound is Ω(3.07n).
[Proof] We consider “folding of the last k+1 unit papers”;
g(k): the number of folding ways of length k+1 s.t.
the leftmost endpoint is not coveredis equal to “the number of ways a semi-infinite
directed curve can cross a straight line k times”,
A000682 in “The On-Line Encyclopedia of Integer Sequences”.
From that site, we have g(43)=830776205506531894760.
nThus, by f (n) ≥ ( g (k )) k −1 =1/( k −1) ng (k )()we have the lower bound.
2020/01/29

I628E: Information Processing Theory

also obtained byenumeration

Open problem and Future work
Minimization of crease width is basically settled;• Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito,
Anna Lubiw, Ryuhei Uehara and Yushi Uno: Folding a Paper
Strip to Minimize Thickness, WALCOM 2015, Lecture Notes inComputer Science Vol. 8973, pp. 113-124, 2015/02/262015/02/28, Dhaka, Bangladesh.
• Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, Hiro Ito, andYoshio Okamoto: Complexity of the stamp folding problem,
Theoretical Computer Science, Vol. 497, pp. 13-19, 2012.

••

Some unsettled problems;

Minimization of crease width for “total” model

For stamp folding problem;•What is the most complex pattern of M/V that has the mostfeasible folded states?

2020/01/29

I628E: Information Processing Theory

Extension of Stamp Folding
2 dimensional → Map Folding Problem
Input: 2 dimensional (orthogonal) M/V pattern
Output: Does it have folded state of size 1×1?
• The complexity of map of size m×n is famous open problem• For map of size 2×n, O(n9) time algorithm was proposed ,but…
• Difficult example;

2020/01/29

I628E: Information Processing Theory