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/27

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/27

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/27

I628E: Information
Processing Theory

Origami?
• In Japanese, “Ori”=folding and “kami/gami”=paper.

• It was born in 1500? with inventing paper, in some Asia,maybe. Of course, we have no record on paper!
• Now, “ORIGAMI” is an English word, and there are someshelves in bookstores in North America and Europe.
• Origami-like things…

There are some “Origami”swhich are not folded, and not
paper any more now a day!!
Maybe by an NSF big fund?
2020/01/27

I628E: Information
Processing Theory

Origami as paper folding• Normal Origami• Difficult Origami• Impossible Origami (for most human!)

Kawasaki Rose

2020/01/27

Maekawa Devil

By Tetsushi Kamiya (Origami Champion)

I628E: Information
Processing Theory

Applications of Origami• There are many applications of“Folding”→ Computational Origami
Foldable Solar Panels(Miura Map Folding)
AirbagSciencebased on thebasic operationsof “folding”
There are many
applications and open
problems of “folding”
Packing

Self-foldable robot
Protein folding problem

2020/01/27

I628E: Information
Processing Theory

Computational ORIGAMI?
• Rapid development of Origami itself• “Complex Origami” were born in 1980s-1990s

Maekawa Devil (1980)
Folded from a squarepaper!

2020/01/27

Kawasaki Rose (1985)

Folded from asquare paper!

Cuckoo clock by Robert Lang(1987)
Folded from a rectangular
Paper of size 1×10!

I628E: Information
Processing Theory

Computational ORIGAMI?
• Computer Aided Design of Origami• Development of origami design by computer since 1990s

Cuckoo clock by Robert Lang Origamizer byRotational symmetry origami(1987)Tomohiro Tachi (2007) by Jun Mitani (2010)
Folded from a rectangularFolded from a
Folded from a rectangular paper
rectangular paper in 10 hours!
Paper of size 1×10!

2020/01/27

I628E: Information
Processing Theory

Research on origami in Computer Science
Popular rather than US/Europe, not Asia ;-)• Development of software with methodology:•••

1980s: Maekawa Devil•
Origin of “complex origami”•
Designed by CAD-like method (by his hand)…including
2000s: TreeMaker by R. Lang
NP-Complete•
It develops a given metric tree
problemonto a square•

It solves some optimization problems
in a practical time

2020/01/27

I628E: Information
Processing Theory

International Conference onOrigami Science
1.

1989@Italy•

2.

1994@Japan•

3.

6.
7.

4OSME

2010@Singapore Proceedings•

Proceedings ison market

3OSME(International meeting of Origami Science, Mathematics, and Education)

2006@USA•

5.

International meeting of Origami Science and Art

2001@USA•

4.

International meeting of Origami Science and Technology

5OSME

2014@Japan• 6OSME
2018@UK• 7OSME
2020/01/27

become 2
volumes

Proceedings
become 4
volumes

I628E: Information
Processing Theory

Computational ORIGAMI?
• Proposal of “Computational Origami”

Since 1990s:
In Computational Geometry area, they consider “foldingproblems” as problems in computational geometry and/oroptimization
The BIG name in this area: Prof. Erik D. Demaine• Born in 1981
• Got Ph.D in Canada when he was 20 years old,and a faculty position at MIT.
• Topic of his thesis was Computational Origami!

2020/01/27

I628E: Information
Processing Theory

Computational ORIGAMI• Bible:Geometric Folding Algorithms: Linkages, Origami, Polyhedra
by J. O’Rourke and E. D. Demaine, 2007.
Authors

2018

I, translated (2009).

Most results canbe found in thisbook…
2011

2020/01/27

2012

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?

Part 3: Recent topics

2020/01/27

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

I628E: Information
Processing TheoryToday…
1. Basic facts for unfolding
2. Polygons foldable two or more boxes
3. Common unfolding of regular polyhedra (or Platonic solids)

2020/01/27

I628E: Information
Processing Theory

Preparation: Unfolding?

• (General) Unfolding: Cut the surface of a polyhedron alongline segments and unfold it onto a plane• It should be connected• It should be a simple polygon without self-overlapping• Edge-Unfolding: Unfolding obtained by cutting along onlyedges
∞ unfoldings★We consider general unfolding today!

11 edge-unfoldings

2020/01/27

I628E: InformationProcessing Theory

Brief history of unfolding“Underweysung der messing” by Albrecht Dürer(1525)• He described polyhedra by edge unfolding• He conjectured the following?

Open Problem：
Any convex polyhedron has an edge unfolding

2020/01/27

I628E: Information
Processing Theory

Brief history of unfolding
Open Problem：
Any convex polyhedron has an edge unfolding

Some related results (which we do not go into):• (Of course) no counterexamples• Counterexamples in concave polyhedra(Any edge unfolding makes overlapping)• Possible in general unfolding(Cut along shortest paths to all vertices from a general point)• If you randomly unfold a random convex polyhedron,it causes overlapping with probability almost 1.

If you are interested in....

Summary: We have few knowledge about unfolding

2020/01/27

I628E: Information
Processing Theory

Brief history of unfolding
Open Problem：
Any convex polyhedron has an edge unfolding
Summary:
We have few knowledge about unfolding
Main Target in this context:••

For a given simple polygon P, what kind of (convex)
polyhedra Q folded from P?
(Algorithm/Mathematical Characterization)
For a given (convex) polyhedron Q, what kind ofsimple polygons P obtained by unfolding of Q?
(Algorithm/Mathematical Characterization)

2020/01/27

I628E: Information
Processing Theory

If you are interested in....

Brief history of unfolding
Summary:
We have few knowledge about unfolding
Main Target in this context:••

For a given simple polygon P, what kind of (convex) polyhedra Q folded fromP? (Algorithm/Mathematical Characterization)
For a given (convex) polyhedron Q, what kind of simple polygons P obtainedby unfolding of Q? (Algorithm/Mathematical Characterization)

Exercise: What polyhedron you can fold?
（１）（２）

From this “Latin Cross”,
you can fold 23 different
convex polyhedra in 85
different ways!
From this “Latin Cross”,
you can fold ∞ different
concave polyhedra!
[found by Uehara, 2014]2020/01/27

I628E: Information
Processing Theory

1. Basic of unfolding (1)Let G be the graph induced by the vertices
and edges of a convex polyhedron Q.
[Spanning tree theorem (1)]
Any set of cut lines of Q for an edge unfolding
Corollary:
On a regular
is a spanning tree of G.
polyhedron, the[Proof]
total cut length of• It visits every vertex of Q:
any edge-unfoldingis the same.
Otherwise, we cannot “lay” on a plane.
• No cycle:
If you have a cycle, the unfolding is disconnected.
[Spanning tree theorem (2)]
Any set of cut lines of Q for a general unfolding is a tree spanning allvertices of Q.
2020/01/27

I628E: Information
Processing TheoryQG

1. Basic of unfolding (2)P

Mathematical characterization of (general)
unfolding of a regular tetrahedron[Unfolding Theorem of a Regular Tetrahedron(Akiyama 2007)]
A polygon P is an unfolding of a regular tetrahedron if and only if it
is a tiling satisfying the following conditions:(1) P is a p2 tiling. (It can “tile” by 180°rotations)(2) 4 rotation centers induce a regular triangular lattice(3) These 4 centers are not “equivalent” on this tiling

Cf： A regular tetrahedron has
2 edge unfoldings

43

1

2

2020/01/27

I628E: Information
Processing Theory

22

3
2

3

4
12

1. Basic of unfolding (2)P

Mathematical characterization of (general)
unfolding of a regular tetrahedron[Unfolding Theorem of a Regular Tetrahedron(Akiyama 2007)]
A polygon P is an unfolding of a regular tetrahedron if and only if it
is a tiling satisfying the following conditions:(1) P is a p2 tiling. (It can “tile” by 180°rotations)Tile-Makers and Semi-Tile Makers,(2) 4 rotation centers induce a regular triangular lattice
Jin Akiyama, The Mathematical(3) These 4 centers are not “equivalent” on this tiling
Association of America, Monthly 114,
pp. 602-609, 2007.

[Intuitive explanation (not proof)]
If you “roll” a regular tetrahedron 4times in a proper way, it will returnto the original position in originaldirection.
So if you put ink on it, you can fill
the plane by this “stamping”.

2020/01/27

I628E: Information
Processing Theory

1. Basic of unfolding (3)Tetramonohedron is atetrahedron consists of 4
congruent acute triangles

P

Mathematical characterization of (general)
unfolding of a tetramonohedron[Unfolding Theorem of a Tetramonohedron(Akiyama and Nara 2007)]
A polygon P is an unfolding of a tetramonohedron if it is a tiling satisfying
the following conditions:(1) P is a p2 tiling. (It can “tile” by 180°rotations)(2) 4 rotation centers induce a triangular lattice (by the triangle)(3) These 4 centers are not “equivalent” on this tiling

Exercise: You can fold atetramonohedron fromany acute triangle.
What happens for an
obtuse triangle?

[Intuitive explanation (not proof)]
You can “bend” the triangular latticein the previous theorem for a regulartetrahedron.

22

2020/01/27

I628E: Information
Processing Theory4312

1. Basic of unfolding: Some Exercises
1. Pick up one, say P, of 11 edge unfolding of a cube. Find as many convex
polyhedra folded from P as you can find. What can you say the conditions
that you can obtain a convex polyhedron from P?
2. Show that you can fold to a tetramonohedron from any acute triangle.
What happens you try to fold from an obtuse triangle? Consider anddiscuss convex and concave quadrilaterals.
3. Find the shortest cut length of regular polyhedra.
• For a regular tetrahedron, we have a beautiful solution.
• Show the optimal solution and proof (if possible)• For a regular octahedron and a cube;• You may find optimal solutions,• But showing the optimality is tough…

• For a regular icosahedron and a dodecahedron;• Finding optimal solutions may be tough?

2020/01/27

I628E: Information
Processing Theory

Computational ORIGAMI=Geometry＋Algorithm＋Computation• Mathematics• Theoretical Computer Science• Real High Performance Computing• Many Applications from micro-size to universe-size• Bioinfomatics (e.g., DNA folding),• Robotics, packaging,• Architecture• Many young researchers;• even undergrad students, highschool students!

2020/01/27

I628E: Information
Processing Theory