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/02/03

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
1. (Bumpy) Pyramid Folding
2. Zipper Unfoldability• 13:30-15:10 (Office Hour at I67-b)

2020/02/03I628E: Information
Processing Theory

Zipper Unfolding ofDomes and Prismoids
Reference:
Erik D. Demaine, Martin L. Demaine and Ryuhei
Uehara: Zipper Unfoldability of Domes and Prismoids,
The 25th Canadian Conference on ComputationalGeometry (CCCG 2013) , pp. 43-48, 2013/08/082013/08/10, Waterloo, Canada.

Since Dűrer (1525), …
Big Open Problem in Computational Origami:
Any convex polyhedron can be developed into a flat
(nonoverlapping) polygonal shape by cutting only
along its edges?

Since Dűrer (1525), …
Big Open Problem in Computational Origami:
In my personal sense, the difficulty comes from
1. “edge cutting”: combinatorics of spanning trees
on a graph (induced by the edges)(cf. any development forms a spanning tree)• if you allow to cut inside of faces, you can get anonoverlapping development.

2. “overlapping”: geometry of the shape of thepolyhedron•

if you don’t mind overlapping, any spanning tree
gives you a “development.”Since Dűrer (1525), …
Big Open Problem in Computational Origami:
We concentrate on “overlapping” with restricted“edge cutting”:“Edge cutting” should be Hamiltonian path;
Hamiltonian unfolding investigated in[Shephard 1975][Demaine2, Lubiw, Shallit2 2010]
Applications:Since Dűrer (1525), …
Big Open Problem in Computational Origami:
We concentrate on “overlapping” with restricted“edge cutting”:“Edge cutting” should be Hamiltonian path;
Hamiltonian unfolding investigated in[Shephard 1975][Demaine2, Lubiw, Shallit2 2010]
Applications:Hamiltonian unfolding
Known results [DDLSS 2010]:
Most regular convex polyhedra are Hamiltonian
unfoldable.
But, e.g., a rhombic dodecahedron
has no Hamiltonian unfolding
because it has
no Hamiltonian path.

Hamiltonian unfolding
A rhombic dodecahedron has no Hamiltonianunfolding since it has no Hamiltonian path.
We introduce/consider Hamiltonian unfolding toconcentrate on overlapping!?
Natural question:
Are there (natural) polyhedra that
1. have many Hamiltonian paths
2. Hamiltonian ununfoldable becauseof overlapping?

Hamiltonian unfolding
Main results:
1. Sequence of domes that

1. have many Hamiltonian paths
2. Hamiltonian ununfoldable because of overlapping!

2. Hamiltonian unfoldability of any nested prismoid
3. Poly-time algorithm for Hamiltonianunfoldability of any (general) prismoid

Hamiltonian unfolding:ununfoldable domes

Dome: convex polyhedron that consists of••

single base (convex n-gon)n sides (convex polygon)•E.g. dome with pentagon base with 5 sides

Th 2: Hamiltonian-ununfoldable domes
Th 2: There exists an infinite sequence ofHamiltonian ununfoldable domes.
[Proof] Constructive. For the following D(i), we have thetheorem for i≧12.
D(3)

D(12)

Th 2: Hamiltonian-ununfoldable domes[Obs 1] We have many Hamiltonian-paths P.
[Obs 2] deg(c)=1 or 2 on any HP P.
[Obs 3] Most qi (≦2 exceptions) are tops of flap.
D(3)

D(12)

Th 2: Hamiltonian-ununfoldable domes[Obs 1] We have many Hamiltonian-paths P.
[Obs 2] deg(c)=1 or 2 on any HP P.
[Obs 3] Most qi (≦2 exceptions) are tops of flap.
D(3)

D(12)

Th 2: Hamiltonian-ununfoldable domes[Obs 1] We have many Hamiltonian-path P.
[Obs 2] deg(c)=1 or 2 on any HP P.
[Obs 3] Most qi are tops of flap.
Overlap should occur for any i≧12!

Hamiltonian unfolding
Main results:
1. Sequence of domes that

1. have many Hamiltonian paths
2. Hamiltonian ununfoldable because of overlapping!

2. Hamiltonian unfoldability of any nested prismoid
3. Poly-time algorithm for Hamiltonian
unfoldability of any (general) prismoid

Hamiltonian unfolding
Main results:
2. Hamiltonian unfoldability of any nested prismoid
Th. 4: Any nested prismoid has aHamiltonian unfolding.
3. Poly-time algorithm for Hamiltonian
unfoldability of any (general) prismoid
Th. 5: The number of HPs in a prismoid withn vertices is O(n3).
Just count it!

PrismoidPrismoid: convex hull of two parallel convex
polygons with matching angles• It has “top” and “bottom,” whose angles match.

Nested prismoid: orthogonal projection of the top isincluded in the bottom.

Hamiltonian unfolding

Main results:
Th. 4: Any nested prismoid has a Hamiltonianunfolding.

Th. 5: The number of HPs in a prismoid withn vertices is O(n3).

Related results
Band of any prismoid (=without top/bottom) can beunfolded by cutting an edge (not any edge).
Nested [Aloupis, et al. 2004/2008]
General [Aloupis 2005](Ph.D Thesis)

Hamiltonian unfolding
Th. 4: Any nested prismoid has a Hamiltonian
unfolding.
Basic idea:
1.
2.
3.
4.

cut the edge to unfold the band
cut its neighbor edge and around top
choose suitable edge to attach the band to base
cut the remaining edges

Hamiltonian unfolding

Main results:
Th. 4: Any nested prismoid has a Hamiltonian
unfolding.

Q: Does it workfor generalprismoid?
A: I don’t know, sofar.

Conclusion
Conjecture:
Any general prismoid has a Hamiltonian unfolding.
(How can we avoid overlap between top and band?)

Nest step:• Prismatoid: convex hull of two parallel convex
polygons••

they have exponentially many HPs
so far, we have no Hamiltonian ununfoldable one (evenfor bands)

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/02/03

I628E: Information
Processing Theory