Introduction to
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)

2020/01/27

I628E: Information
Processing Theory

Common Unfolding ofUsed as
multiple boxes• Common unfolding of two boxes• Common unfolding of three boxes• And open problems….

2020/01/27

I628E: Information
Processing Theory

main trick ina mysterynovel

References• Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, Ryuhei Uehara: CommonDevelopments of Three Incongruent Boxes of Area 30, COMPUTATIONALGEOMETRY: Theory and Applications, Vol. 64, pp. 1-17, August 2017.
• Toshihiro Shirakawa and Ryuhei Uehara: Common Developments of Three
Incongruent Orthogonal Boxes, International Journal of Computational
Geometry and Applications, Vol. 23, No. 1, pp. 65-71, 2013.
• Zachary Abel, Erik Demaine, Martin Demaine, Hiroaki Matsui, Guenter Roteand Ryuhei Uehara: Common Developments of Several Different OrthogonalBoxes, Canadian Conference on Computational Geometry (CCCG' 11), pp. 7782, 2011/8/10-12, Toronto, Canada.
• Jun Mitani and Ryuhei Uehara: Polygons Folding to Plural Incongruent
Orthogonal Boxes, Canadian Conference on Computational Geometry (CCCG
2008), pp. 39-42, 2008/8/13.
2020/01/27

I628E: Information
Processing Theory

In,• There were two unfoldings that fold to two boxes;• Are they exceptional?
• Is there any unfoldingthat fold to 3 or moreboxes??

[Biedl, Chan, Demaine, Demaine, Lubiw, Munro, Shallit, 1999]

2020/01/27

I628E: InformationProcessing Theory

Unfolding of two boxes

In [Uehara, Mitani 2007], randomized
algorithm that looks for such polygons bybrute force;• Polygons folding into 2 boxes:
1. There are many (～9000)(by supercomputer (SGI Altix 4700))

2. Theoretically,
infinitely many

2020/01/27

I628E: Information
Processing Theory

Simple Observation:

Example：1×1＋1×5＋１×5＝1×2＋2×3＋1×3＝11 （surface area: 22)• Polygons folding to 2 different boxes

1×1×5=a×b×c• We fold/(cut) at an edge ofunit squares• Surface area: 2(ab + bc + ca)• Necessary condition:
ab + bc + ca = a ' b '+ b ' c '+ c ' a '2020/01/27

I628E: Information
Processing Theory

1×2×3= a’ × b’ × c’
It is better to have
many combinations…

If you try to find for three boxes,

Simple Computation:

If you try to find for four boxes,

Surface areas;
Area

TriosArea

Trios

22
30
34

(1,1,5),(1,2,3)(1,1,7),(1,3,3)(1,1,8),(1,2,5)

46
70
94

38

(1,1,9),(1,3,4)known
118(1,1,11),(1,2,7),(1,3,5)(1,1,17),(1,2,11),(1,3,8),(1,5,5)(1,1,23),(1,2,15),(1,3,11),(1,5,7),(3,4,5)(1,1,29),(1,2,19),(1,3,14),(1,4,11),(1,5,9),(2,5,7)

results

My past student proved that for any k, there isa surface area which has k trios!
2020/01/27

I628E: Information
Processing Theory

Unfolding of two boxes[Theorem] There exists an infinitely many
unfoldings that fold to 2 boxes.
1.copy this area, and2.paste it k times as in figure.

[Proof]j

2020/01/27

I628E: Information
Processing Theory

Unfolding of two boxes[Theorem] There exists an infinitely many
unfoldings that fold to 2 boxes.
[Proof]j

1 × 1 × ((2j+2)k+11)
2020/01/27

I628E: Information
Processing Theory

Unfolding of two boxes[Theorem] There exists an infinitely many
unfoldings that fold to 2 boxes.
[Proof]

1 × j × (4k+5)j2020/01/27

I628E: Information
Processing Theory

Unfolding of three boxes(?)• A polygon that can fold to three distinct boxes…?
close one…
1×5×5

1×3×8 ±2

1×1×172020/01/27

I628E: Information
Processing Theory

Unfoldings of three boxes (without computer!)• In February 2012,
Shirakawa (and I) finallyfound a polygon thatfolds to 3 boxes!!
[Basic Idea] From an unfolding of
2 boxes, we make one more box.

Available at
http://www.jaist.ac.jp/~uehara/etc/origami/nets/3box.pdf
2020/01/27

I628E: Information
Processing Theory

Unfoldings of three boxes (without computer!)• In February 2012,
Shirakawa (and I) finallyfound a polygon thatfolds to 3 boxes!!
[Basic Idea] From an unfolding of
2 boxes, we make one more box.

Available at
http://www.jaist.ac.jp/~uehara/etc/origami/nets/3box.pdf
2020/01/27

I628E: Information
Processing Theory

Unfoldings of three boxes (without computer!)• In February 2012,
Shirakawa (and I) finallyfound a polygon thatfolds to 3 boxes!!
[Basic Idea] From an unfolding of
2 boxes, we make one more box.

Available at
http://www.jaist.ac.jp/~uehara/etc/origami/nets/3box.pdf
2020/01/27

I628E: Information
Processing Theory

Unfoldings of three boxes (without computer!)• In February 2012,
Shirakawa (and I) finallyfound a polygon thatfolds to 3 boxes!!
[Basic Idea] From an unfolding of
2 boxes, we make one more box.
One more box
is obtained bythis squashing!?

ab[No!!]
This works iff a=2b, i.e.,from 1×2 rectangle to2×1 rectangle!

Available at
http://www.jaist.ac.jp/~uehara/etc/origami/nets/3box.pdf
2020/01/27

I628E: Information
Processing Theory

Unfoldings of three boxes (without computer!)• In February 2012,
Shirakawa (and I) finallyfound a polygon thatfolds to 3 boxes!!
[Basic Idea] From an unfolding of
2 boxes, we make one more box.

[Yes… with a trick!]This idea works;
move a part ofthe lid to 4 sides!

Available at
http://www.jaist.ac.jp/~uehara/etc/origami/nets/3box.pdf
2020/01/27

I628E: Information
Processing Theory

Unfoldings of three boxes (without computer!)• In February 2012,
Shirakawa (and I) finallyfound a polygon thatfolds to 3 boxes!!
[Basic Idea] From an unfolding of
2 boxes, we make one more box.

Available at
http://www.jaist.ac.jp/~uehara/etc/origami/nets/3box.pdf
2020/01/27

I628E: Information
Processing Theory

Unfoldings of three boxes (without computer!)• In February 2012,
Shirakawa (and I) finallyfound a polygon thatfolds to 3 boxes!!
[Basic Idea] From an unfolding of
2 boxes, we make one more box.

[Generalization!]• Basic box is flexible forthe edge lengths.
• Zig-zag pattern can beextended.

[Theorem]
There exist an infinite number of
Available at polygons that fold into 3 different boxes.
http://www.jaist.ac.jp/~uehara/etc/origami/nets/3box.pdf
2020/01/27

I628E: Information
Processing Theory

Open Problems so far• Smallest unfolding?

The current “smallest” unfolding requires
532 squares in this method.
>> the smallest area 46 that may produce
three boxes of size (1,1,11), (1,2,7), (1,3,5).
(We know: 2263 polygons of area 22 folding to (1,1,5), (1,2,3)
by 10 hours enumeration in 2011)

Is there a polygon that folds to 4 or more boxes?
2020/01/27

I628E: Information
Processing Theory

Email from my puzzle friend on October 2012:“I find unfolding of area 30 that can fold to boxes of size
1×1×7 and √5×√5×√5. This area allows us to fold
1×3×3. So there may be a smallest polyomino that fold tothree boxes if you allow to fold along diagonal.”

2020/01/27

I628E: Information
Processing TheoryIf you try to find for three boxes,

Observation

If you try to find for four boxes,

Surface areas;

Area

Trios

Area

Trios

22
30
34

(1,1,5),(1,2,3)(1,1,7),(1,3,3)(1,1,8),(1,2,5)

46
70
94

38

(1,1,9),(1,3,4)known
118(1,1,11),(1,2,7),(1,3,5)(1,1,17),(1,2,11),(1,3,8),(1,5,5)(1,1,23),(1,2,15),(1,3,11),(1,5,7),(3,4,5)(1,1,29),(1,2,19),(1,3,14),(1,4,11),(1,5,9),(2,5,7)

results

Program in 2011:“Area 30” sounds tractable…?
• Enumeration of all unfolding of area 22：• Two boxes of sizes 1×1×5 and 1×2×3 have 2263 common unfolding• It run in 10 hours by a usual PC

2020/01/27

I628E: Information
Processing Theory

My past student succeeded! (June, 2014)• We succeeded to enumerate all unfolding of area 30[Xu, Horiyama, Shirakawa, Uehara 2015]• Summary• It took 2 months on a supercomputer (Cray XC 30) in JAIST.
• We have 1080 common unfolding of two boxes of size 1×1×7 and 1×3×3• Among them, we have 9 polyominoes that fold to the third box of size
√5×√5×√5

We had a “serendipity”(unexpected discovery):The (2) and (4) have four
different ways to foldthree different boxes!!

2020/01/27

I628E: Information
Processing Theory

If you try to find for three boxes,

Summary

If you try to find for four boxes,

Area

Trios

Area

Trios

22
30
34

(1,1,5),(1,2,3)(1,1,7),(1,3,3)(1,1,8),(1,2,5)

46
70
94

38

(1,1,9),(1,3,4)

118(1,1,11),(1,2,7),(1,3,5)(1,1,17),(1,2,11),(1,3,8),(1,5,5)(1,1,23),(1,2,15),(1,3,11),(1,5,7),(3,4,5)(1,1,29),(1,2,19),(1,3,14),(1,4,11),(1,5,9),(2,5,7)

We need more sophisticatedBrute Force works:
algorithms/ideas to explore more…
• Area 22： 10 hours on a PC in 2011• Area 30: 2 months on a supercomputer in 2014
• Using BDD (Binary Decision Diagram), it is improved to 10 days in 20152020/01/27

I628E: Information
Processing Theory

Open problems• Is there common unfolding of area 46 or 54 thatcan fold to three boxes?
• Is there common unfolding of 4 or more boxes?
• Is there upper bound of k such that “there is nocommon unfolding of k or more boxes”?
• It is quite unlikely that one polygon can fold 10000
different boxes…?

2020/01/27

I628E: Information
Processing Theory

Recent work and future work
• More general problem:

For a given polygon P and a convex polyhedron Q, determine if
P can fold to Q or not.

Known/related results：

1. There is a general pseudo-polynomial time algorithm for generalpolygon P and convex polyhedron Q, but…
• The algorithm runs in O(n456.5) time! (Kane, et al, 2009)
2. We solved if Q is “some box”; (size is not given)• Koichi Mizunashi, Takashi Horiyama, and Ryuhei Uehara: Efficient Algorithm for
Box Folding, Journal of Graph Algorithms and Applications, accepted, 2019.

There are many unsettled problems between them!
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 space-size• Bioinfomatics (e.g., DNA folding),• Robotics, packaging,• Architecture• Many young researchers;

Let’s join it!

• even undergrad students, highschool students!

2020/01/27

I628E: Information
Processing Theory