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Reference:

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, Vol. 27, pp. 341-351, 2011.
Belgium

JAIST

Waterloo

Nagoya U.

NII• 2020/01/29 • I628E: Information Processing TheoryMIT• Repeating of mountain andvalley foldings• Basic operation in some origami• Many applications

Fold and…

steam

http://km-sewing.seesaa.net/article/60694279.htmlTokyo Monorail

Bus to JAISTRepeating “folding in half” isthe best way to make manycreases.

Pleat folding• Pleat folding (in 1D)• Naïve algorithm: n time folding is a trivial solution• We have to fold at least log n times to make n creases• More efficient ways…?
• General Mountain/Valley pattern?
• proposed at Open Problem Session on

CCCG 2008 by R. Uehara.
• Many people get together with some ideas.
2020/01/29

I628E: Information Processing Theory

Model：Paper has 0 thickness• Complexity of Pleat Folding[Main Motivation] Do we have to make n foldings
to make a pleat folding with n creases??
1. The answer is “No”!

 Any pattern can be made by  n / 2  + log n  foldings

2. Can we make a pleat folding in o(n) foldings?
 Yes!! …it can be folded in O(log2 n) foldings.

3. Lower bound; log n•(We stated Ω(log2 n/loglog n) lower bound for pleat folding!!)• Complexity of Pleat Folding[Next Motivation] What about general pleat folding
problem for a given M/V pattern of length n?
1.

 Any pattern can be made by  n / 2  + log n  foldings

Upper bound: n nAny M/V pattern can be folded by (4 + ε )+ o foldings

log n

2.

Lower bound:
Almost all mountain/valley patterns require log n nfoldings
3 + log n[Note] Ordinary pleat folding is exceptionally easy pattern!

Difficulty/Interest come from two kinds of Parities:• “Face/back” determined by layers• Stackable points having the same parity• Def: Unit Folding Problem
Input: Paper of length n+1 and a string s in {M, V}n
Output: Well-creased paper according to s at regular intervals.
Basic operations
1.
Flat {mountain/valley} fold {all/some} papers at an integer point (=simple folding)
2. Unfold {all/rewind/any} crease points (= reverse of simple foldings)
Rules
1.
2.

Each crease point remembers the last folded direction
Paper is rigid except those crease points

Goal: Minimize the number of folding operations
Note: We ignore the cost of unfoldings• Upper bound of Unit FP (1) Any pattern can be made by  n / 2 + log n  foldings
1. M/V fold at center point according to the assignment
2. Check the center point of the folded paper, and count the
number of Ms and Vs (we have to take care that odd depthpapers are reversed)
3. M/V fold at center point taking majority
4. Repeat steps 2 and 3
5. Unfold all (cf. on any model)
6. Fix all incorrect crease points one by one
Steps 1~4 require log n and step 6 requires n/2 foldings

Upper bound of Pleat Folding(1)[Observation]
If f(n) foldings achieve n mountain foldings,n pleat foldings can be achieved by 2 f(n/2) foldings.
The following strategy works;• Make f(n/2) mountain foldings at odd points;• Reverse the paper;• Make f(n/2) mountain foldings at even points.
We will consider the“mountain folding problem”

CF： O(n0.69) algorithm[Th] Mountain folding problem can be solved in O(n0.69) time
[Proof] Let n=2k, and use the following algorithm;
1. Fold the leftmost point to make length 2k-1
2. Fold in half at the central point
2. Repeat [2] up to length 1
4. Open all…
MV2
34
56
By k+1 folding, we have 2k-1+1 mountains & 2k-1-1 valleys

2124801248

CF： O(n0.69) algorithm[Th] Mountain folding problem can be solved in O(n0.69) time
[Proof]
234562124801248

2k-1-1 valleys can be split into k-1 independent and uniformlayers!!
∴ f (2 k ) =1 + k + f (2k − 2 ) + f (2k −3 ) +  + f (4) + f (2) + f (1)f (2k −1 ) =k+f (2k −3 ) +  + f (4) + f (2) + f (1)f (2k ) − f=
(2k −1 ) f (2k − 2 ) + 1
Fibonacci sequence for k !
kk −1
k −2
=
( f (2 ) + 1) ( f (2 ) + 1) + ( f (2 ) + 1)

CF： O(n0.69) algorithm[Th] Mountain folding problem can be solved in O(n0.69) time
[Proof]Fibonacci sequence for k !

=( f (2k ) + 1) ( f (2k −1 ) + 1) + ( f (2k − 2 ) + 1) [Fibonacci sequence]

Initial state：=f (20 ) 1,=f (21 ) 2,=f (22 ) 4
f (2k ) + 1 =Fk +3Thus

F0=0, F1=1, Fi=Fi-1+Fi-2 (i>1)
0,1,1,2,3,5,8,13,21,34,…

=
Fiii1   1 + 5   1 − 5   −
5   2   2  k +3k +3k +3







11+ 51− 5
1 1+ 5k∴ f ( n) =f (2 ) =
−1 
 − 
5  2 
5 2 
 2    1 + 5 log n  log1+ 5 0.694242)= O   = n 2  O(n  O=
 2  Mountain folding in log2 n foldings
Step 1;
1.
2.
3.

Fold in half until it becomes of length [vvv] (log n-2 foldings)
Mountain fold 3 times and obtain [MMM]
Unfold; vMMMvvvvvMMMvvvvvMMMvvvvvMMMvvvvv…

Step 2;
1.
2.
3.

[MvvvvvM]

Fold in half until all “vvvvv”s are piled up (log n-3 foldings)
Mountain fold 5 times [MMMMMMM], and unfold
vMvMMMMMMMvMvvvvvMvMMMMMMMvMvvvvvMvM

Step 3; Repeat step 2 until just one “vvvvv” remainsvMvMMMvMMMvMMMMMMMvMMMvMMMvMvvvvvMvM

Step 4; Mountain fold all irregular vs step by step.
• #iterations of Steps 2~3; log n• #valleys at step 4; log n#foldings in total~ (log n)2• Lower bound of Unit FP[Thm] Almost all patterns but o(2n) exceptions requireΩ(n/log n) foldings.
{surface/reverse}×{front/back}[Proof] A simple counting argument:• # patterns with n creases > 2n/4 = 2n-2
• # patterns after k foldings <(2×n)×(n+1)×(2×n)×(n+1)×…×(n+1)×(2×n)
M/V<(2n(n+1))kPositionPossible unfoldings• We cannot fold most patterns after at most k foldings ifk• Letting∑ (2n(n + 1)) ≤ (2n(n + 1) + 1) < 2iki =0

 n n ≥ 2, k =O we have log n 

(2n(n + 1) + 1) k =o(2n )n−2Any pattern can be folded in cn/log nfoldings
Select suitable b
depending on n.

Prelim.
•2.

Each chunk is small and easy to fold#kinds of different bs are not so big

Main alg.
For each possible b
1.

pile the chunks of pattern b andmountain fold them2.

fix the reverse chunks
fix the boundaries

3.

bbb

want to fold “ “sSplit into chunks of size b;
1.

•b

pileOKNOKsOK

Half chunks are done!
Fold NOKs again

Repeat for all chunks
Analysis is omitted

• Open Problems•

Pleat foldings•

Make upper bound O(log2 n) and lower bound Ω(log2 n /loglog n)closer• “Almost all patterns are difficult”, but…
•No explicit M/V pattern that requires (cn/log n) foldings• When “unfolding cost” is counted in…
•

Minimize #foldings + #unfoldings• Extension to 2 dimensional and general intervals