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

I628E Information Processing Theory• Schedule• January 27 (13:30-15:10)• Introduction to Computational Origami• Polygons and Polyhedra folded from them

• January 29 (10:50-12:30)• Computational Complexity of Origami algorithms• February 3 (9:00-10:40)• Advanced topics• 13:30-15:10 (Office Hour at I67-b)

2020/01/29

I628E: InformationProcessing Theory

I628E Information Processing Theory• Report (up to 20pts)• Submit a report about one of the following two options:
1. Survey some paper(s) appearing in these three lectures
2. Solve some problems appearing in these three lectures• Firm deadline: 17:00, February 10 in one of the following
two ways• By email:PDF file (word file is not acceptable) from JAIST account.
• By paper:
A4 size paper, staple at the top-left corner.
You can write your report in English or Japanese.

2020/01/29

I628E: Information
Processing Theory

Topics in the lectures

ComputationalGeometry

Part 1: Polygons and polyhedra folded from them

• Relationship between unfolding and solids: Big open problem• How can we compute (convex) “polyhedra” from a given “unfolding”?
• Mathematical characterization/algorithms/computation power

Algorithms andComputational Complexity
Part 2: Algorithms and computational complexity of “folding”• Basic operations of origami• Algorithms and complexity of origami• Efficiency of folding of 1-dimensional origami (algorithms and complexity)• Efficient algorithm (how can we reduce the number of folding?)• How can we evaluate “good” folded states?

Part3: Recent
I havenot yet topics
reach to2-dimension…

2020/01/29

There are many open problems,
where many young researchers working on

I628E: Information
Processing Theory

History…
Kawasaki Rose•

June 22, 2008
at “Forth Origami in Science, Mathematics, andEducation”,

Professor Toshikazu Kawasaki, who is a mathematician and thedesigner of Kawasaki Rose, said that:“As a mathematician, I do not take care once if we can show
the existence of solutions.”

As a computer scientist, I considered…
It is important that how canwe obtain the solution, andIt’s computational cost••

GOOD algorithms?
Computational complexity

We need good problem…
2020/01/29

I628E: Information
Processing Theory

Trivia: The other twin
Kawasaki is a professor of ORin Kyushu University.

Objective: Estimate “Complexity” of origami design

I would like to give the answer to the question“which is more complex?”
You need to fold in 3 dimensional
space. For Uehara, it took 10days at first, but now it takes
about 10 minutes.

Kawasaki Rose

For Uehara, it took 40 minutes,and even Maekawa-san needs
20 minutes to fold.

Maekawa Devil

Both are more complicated than the classic “crane”, but
why can you say that?
2020/01/29

I628E: Information
Processing Theory

Computational complexity andalgorithm theory• Basic theory of theoretical computer science• Basic machine models:Common agreement of “basic operations”• Turing machine• VRAM model• Algorithm = sequence of basic operations• How can we combine basic operations?

• Complexity of algorithm• Time complexity: Estimate by the number of basic
operations• Space complexity: Estimate by the quantity of memory cells

2020/01/29

I628E: Information
Processing Theory

“Complexity” of folding…?
• Basic origami operations:• In origami society, they agree that the following seven
operations as “basic operations”• We consider them as “basic operations”

Hatori’s operation A7
Huzita’s axioms A1-A6

2020/01/29

These 7 operations can solve up to quartic (4) equations.
(Traditional “ruler+compass” can solve up to quadratic(2) equations.)

I628E: Information
Processing Theory

“Complexity” of folding…?
• “Reasonable” origami models to investigate
computational complexity? (Simple → Complex)
1. The simplest model: 1D, creases in unit distance• On a long paper strip, we fold along vertical crease lines of unit
interval

2. 2 directions to extend• Crease lines in non-unit interval• (Crease lines can be slanted)• Higher dimensions (2 or 3 or more?)

2020/01/29

I628E: Information
Processing Theory

We are still around
here…

Complexity/Efficiency of Origami(?)• From the viewpoint of Theoretical Computer
Science…
• Two resources of Turing machine model
1. Time: The number of basic operations
2. Space: The quantity of memory cells

Complexity/Efficiency of Origami(?)• From the viewpoint of Theoretical Computer Science…
• Two resources of Origami model
1. Time: The number of basic (folding) 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, Graphsand Combinatorics, Vol. 27, pp. 341-351, 2011.
(Guoxin Hu, Shin-Ichi Nakano, Ryuhei Uehara and Takeaki Uno: Simple Foldand Cut Problem for Line Segments, CCCG 2019, pp. 158-163, 2019/08/08-10,
Edmonton, Canada.)

2. Space: The quantity of ??
•••R. Uehara: On Stretch Minimization Problem on Unit Strip Paper, 22nd Canadian
Conference on Computational Geometry, pp. 223-226, 2010/8/9-11.
Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, and Hiro Ito: Complexity of thestamp folding problem, 5th Annual International Conference on Combinatorial
Optimization and Applications (COCOA '11), Lecture Notes in Computer Science,Vol. 6831, pp. 311-321, 2011/8/4-6, Zhangjiajie, China.
Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei
Uehara and Yushi Uno: Folding a Paper Strip to Minimize Thickness, The 9thWorkshop on Algorithms and Computation (WALCOM 2015), Lecture Notes in
Computer Science Vol. 8973, pp. 113-124, 2015/02/26-2015/02/28, Dhaka,Bangladesh.

Today’s Topic

The 7th EATCS/LA Presentation Award!

5. Time Complexity••“Folding complexity”

Theoretically, the world fastest algorithm for pleat folding

6. Space Complexity (?)•••

Stamp Folding Problem
Minimization of Crease width

NP-complete problem, FPT algorithm

7. Undecidable Origami Problem•Diagonalization and undecidability

On the other hand; This paper was rejected by some journal because“the proof is too simple”, which is an important point in the paper ;-)Sometimes, it is difficult to propose new computation model…

March 2012IPSJ Yamashita SIG
Research Award

Exercise (or challenge)
1. Propose some measurement that evaluate“complexity” of origami• Example: space for folding

2. Discuss about the measurement• Example: For one dimensional origami, the space forfolding can be important. Imagine folding a long, say,1km, metal pipe for water supply. On the other hand, in
two dimensional space, Origami (in square) basicallyshrinks in each folding usually, so it is not reasonable.
Goal: In Turing machine, we have “time-space trade off”. It isquite nice to have such a measure that has a kind of trade off
property between the number of folding.