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

Today…
1. Basic facts for unfolding
2. Polygons foldable two or more boxes
3. Common unfolding of regular polyhedra (or Platonic solids)
1. Common unfolding of a regular tetrahedron and a cube
2. Common unfolding of a regular tetrahedron and JohnsonZalgaller solids

2020/01/27

I628E: Information
Processing Theory

Common Unfoldingof Regular Tetrahedronand Johonson-Zalgaller SolidReference:•Yoshiaki Araki, Takashi Horiyama, and Ryuhei Uehara.
Common Unfolding of Regular Tetrahedron and JohnsonZalgaller Solid, Journal of Graph Algorithms and Applications,Vol.20, no.1, pp.101-114, February, 2016.
DOI:10.7155/jgaa.00386

I628E: Information
2020/01/27
WALCOM 2015 (Feb. 28th, 2015)
Processing Theory3

Common Unfolding• Theorem : There exists no polygon P s.t.
(1) P is a general unfolding ofa regular tetrahedron(2) P is an edge unfolding of[Horiyama,Uehara 2010]

a regular cube• a regular octahedron• a regular dodecahedron• a regular icosahedron•• Open• General unf.
v.s. General unf.
• General unf. among
4

Common Unfolding• Cube v.s. Tetramonohedron[ Shirakawa, Horiyama,Uehara 2011 ]2 3 ±εε < 2.89×10 -1796

5

Our work• Regular tetrahedron (general unfolding)v.s. Convex polyhedron with regular polygonal faces(edge unfolding)• Platonic solids• face : 1 type of regular polygon• vertex : same face-arrangement[ Horiyama,Uehara 2010 ]• Archimedean solids• face : 2+ types of regular polygons• vertex: same face-arrangement• n-gonal prism• face : 2 regular n-gons & n squares• n-gonal antiprism• face : 2 regular n-gons & 2n regular triangles• Johnson-Zalgaller solids
2020/01/27

I628E: Information
Processing Theory

6

Our Results• Johnson-Zalgaller solids : 92 solids• J17 (Gyroelongated square dipyramid)
has common unfolding with
• J84 (Snub disphenoid)
has common unfolding with

• Archimedean solids
No common unfolding• n-gonal prismwith• n-gonal antiprism• other 90 Johnson-Zalgaller solids
2020/01/27

I628E: Information
Processing Theory

7

Our Results• Johnson-Zalgaller solids : 92 solids• J17 (Gyroelongated square dipyramid) 13,014 edge unfolding 78 unf. : 1 way
8 unf. : 2 ways of folding into
1 unf. : 3 ways
• J84 (Snub disphenoid)
1,109 edge unfolding

32 unf. : 1 way
5 unf. : 2 waysof folding into

• Archimedean solids
No common unfolding• n-gonal prismwith• n-gonal antiprism• other 90 Johnson-Zalgaller solids
2020/01/27

I628E: Information
Processing Theory8Our Results• J17 (Gyroelongated square dipyramid)

2020/01/27

I628E: Information
Processing Theory9

Our Results• J84 (Snub disphenoid)

2020/01/27

I628E: Information
Processing Theory10

By the way,

• Number of edge unfolding of JZ solids [ Horiyama, Shoji 2013 ]
• J01
8
• J02
16
• J03
308
• J04
3,030
207穣 9942𥝱𥝱 3173垓 9411京• J05
29,767986兆 8961億 8195万 6672
• J06 7,825,005•…
• J71 2,079,942,317,394,110,986,896,181,956,672• J72 20,668,673,558,050,742,614,946,330,896• J73 10,597,511,106,353,370,064,654,696,448•…

We cannot check all edge unfolding of them!!

2020/01/27

I628E: Information
Processing Theory

11Outline of “filtering”
Obs: Most JZ solids seem to have no edge unfoldingthat can fold to a regular tetrahedron• We negatively check edge unfolding of each convex
polyhedra;
1. If it has no edge unfolding tiling, we cannot fold any
tetramonohedron.
•We found previous results in [Akiyama et al. 2011]

2. If its area and length have no consistency, we cannot foldto a regular tetrahedron.
3. If some solids pass these tests, we have to try all possiblecombinations in any way…
Mainly I show 2 and 3.

2020/01/27

I628E: Information
Processing Theory

12

Two points• Point 1 :• Why always “(Regular) tetrahedron v.s. ...” ?
We can use “tiling” property!

• Point 2 :• How to obtain edge unfolding ?
We need some (non-trivial) algorithm…

2020/01/27

I628E: Information
Processing Theory

13

Edge unfolding which tiles
1. Some edge unfolding can be tiling for [ Akiyama
et al. 2011 ]:• JZ Solids (18): J1, J8, J10, J12, J13, J14,J15, J16, J17, J49, J50, J51,J84, J86, J87, J88, J89, J90• Regular 6 anti-prism

Note 2: Luckily, they
consist of only regulartriangles and squares.

Note 1: Actually, in [Akiyama et al 2011],
they consider “tiling”, but we have toconsider p2 tiling.

Other solids have no unfolding that can tile the plane

2. Check the consistency of “length” and “area” of the solids
and a regular tetrahedron…
2020/01/27

I628E: Information
Processing Theory

Check the consistency of “length”
and “area”• For each Jx that has tiling unfolding,

1. Find its area Sx
2. Find the edge length Lx of a regular tetrahedron ofarea Sx
3. Consider a partial tiling by △s and □s that form Jx
4. Lx should be made by two grid points on this partialtiling.

I skip somelemmas…

2020/01/27

J15

J16

J17

I628E: Information
Processing Theory

J49

J50

J51

Except J17, J84…
• For each Jx that has tiling unfolding,
3. Consider a way by filling △s & □s that may fold to Jx,
which we called “partial development”
4. On this partial development, we check if there are apair of grid points that makes Lx
5. They make a simple linear summation of √2 and √3.
Thus we cannot make, e.g.,. Thus it cannot
fold to that Jx.

Last survivors: J17, J84, with J12, J13, J14, J51, J89

2020/01/27

I628E: Information
Processing Theory

16

Except J17, J84…
• For each Jx in J12, J13, J14, J51, J89,
3. Enumerate a way by filling △s & □s that may fold to Jx.
4. On this partial development, we check if there are apair of grid points that makes Lx

Conference version

For J12, J13, J14, J51, J89, this check took 10 hours…
Using the vectors, since they can be “sorted”, thecomputation time become less than 1 second!!
Journal version

2020/01/27

I628E: Information
Processing Theory

After 1 year,I found thatwhen I wrote
a journal paper

17Our Results• Johnson-Zalgaller solids : 92 solids• J17 (Gyroelongated square dipyramid) 13,014 edge unfolding 78 unf. : 1 way
8 unf. : 2 ways of folding into
1 unf. : 3 ways
• J84 (Snub disphenoid)
1,109 edge unfolding

32 unf. : 1 way
5 unf. : 2 waysof folding into

For •J17
and J84, weArchimedeansolids
commonwhounfolding
1. First
enumerate
all ways of edge unfolding (byNoHoriyama-sanis an• n-gonal
prism
expert for using a data structure BDD).
with•n-gonalantiprism
2. Since they are not so HUGE, we check each edge unfolding if it is a p2 tiling.
• otherJohnson-Zalgallersolids… How
can we90
checkit?
2020/01/27

I628E: Information
Processing Theory18

Folding problem• In general, the following folding problem is not easy:
Input: Simple polygon P and a convex polyhedron Q
Output: Determine if P can fold to Q
(and we like to have crease lines if P can fold to Q).
The our problem has nice properties;• P consists of regular triangles• Q is a regular tetrahedronHence our algorithm checks if P is a p2 tiling.

2020/01/27

I628E: Information
Processing Theory

We have nogeneral algorithm
so far…

19

Algorithm for J17, J84• Enumeration of edge unfolding is done [ Horiyama, Shoji 2011, 2013 ]• We have• J17 13,041• J84 1,109

RegularTetrahedron

J171x 16

2x4• Cyclic list keeps inner angle at each vertex• (and central point of length ½ for gluing)

I omit in this class• 60, 180, 120, 180, 180, 180, 60, 180, 300, 180, 60, 180, 300, 180, 60,180, 300, 180, 60, 180, 120, 180, 180, 180, 60, 180, 300, 180, 60, 180,300, 180, 60, 180, 300, 180• Guess two rotational centers r1, r2, and check r1 r2 = 2
2020/01/27

I628E: Information
Processing Theory

20

Algorithm for J17, J84• 60, 180, 120, 180, 180, 180, 60, 180, 300, 180, 60, 180, 300,180, 60, 180, 300, 180, 60, 180, 120, 180, 180, 180, 60, 180,300, 180, 60, 180, 300, 180, 60, 180, 300, 180• For the two rotational centers r1, r2, rotate 180°at r1, r2
2020/01/27

I628E: Information
Processing Theory

21

Algorithm for J17, J84• 180,180,240,180, 300,180, 60, 180, 300, 180, 60, 180, 120, 180, 180, 180, 60, 180,300, 180, 60, 180, 300, 180, 60, 180, 300, 180• For the two rotational centers r1, r2, rotate 180°at r1, r2
2020/01/27

I628E: Information
Processing Theory

22

Algorithm for J17, J84• 180,180,240,180, 300,180, 60, 180, 300, 180, 60, 180, 120, 180, 180, 180, 60, 180,300, 180, 60, 180, 300, 180, 60, 180, 300, 180• Guess the third rotational center r3, rotate 180°at r3,and find r4
2020/01/27

I628E: Information
Processing Theory

23

Algorithm for J17, J84• Guess the third rotational center r3, rotate 180°at r3,and find r4• Determine if r1, r2, r3, r4 form a regular triangular lattice or not.
2020/01/27

I628E: Information
Processing Theory24Summary• Johnson-Zalgaller solids : 92 solids• J17 (Gyroelongated square dipyramid) 13,014 edge unfolding 78 unf. : 1 way
8 unf. : 2 ways of folding into
1 unf. : 3 ways
• J84 (Snub disphenoid)
1,109 edge unfolding

32 unf. : 1 way
5 unf. : 2 waysof folding into

• Archimedean solids
No common unfolding• n-gonal prismwith• n-gonal antiprism• other 90 Johnson-Zalgaller solids
2020/01/27

I628E: Information
Processing Theory25

Open problems(or tough exercises)• How about other solids except a regular tetrahedron?
• Existence/non-existence of common unfolding• Edge unfolding/general unfolding• Few days ago, Kamata-kun and Uehara found thatsome pairs of solids can be transformed with eachother by “twisting”. Can they have common unfolding?

2020/01/27

I628E: Information
Processing Theory26