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)
I628E: Information
Processing TheoryBumpy Pyramid Folding
Reference:
Zachary R. Abel, Erik D. Demaine, Martin L. Demaine,
Hiro Ito, Jack Snoeyink, and Ryuhei Uehara. Bumpy
Pyramid Folding, COMPUTATIONAL GEOMETRY:
Theory and Applications, Vol 75, pp. 22-31, December
2018. DOI:10.1016/j.comgeo.2018.06.007

(Bumpy) Pyramid folding
problem
Computational Origami
Input:
Petal••

Base of convex polygon
Petals with matching lengths

Base

Output:it folds into (bumpy) pyramid?

Background story
My old puzzle friend sent me a postal mail…
1. Origami Problem 1:

Input: triangle with three petals (edges are matching)
Output: Does it fold to tetrahedron?
Ans： “YES” if edges are sufficiently long.

2. Origami Problem 2:

Input: quadrilateral with four petals
Output： Does it fold to pyramid?
Obs: In general, we have two ways of folding, and one
gives convex, and the other gives concave?

(Bumpy) pyramid folding problem
Input: A convex n-gon with petals
Problem 1: Does it fold to n-gonal pyramid?
In general, the answer is “NO”, but wehave some solids from it.
Each triangulation of
the base gives distinct
convex/concave solid…

(Bumpy) pyramid folding problem
Input: A convex n-gon with petals
Problem 2: In the case of “NO,”

Problem 2-1: Can we have a convex polyhedron?
Problem 2-2: Can we find a polyhedron withmaximum volume?
Meta-Problem 2: Can the solutions of 2-1 and 2-2 bedifferent?
Meta2-Problem 2：When can we have the same
solution for 2-1 and 2-2?

Related Results
1. Alexandrov’s Theorem (1941)
For every convex polyhedral metric, there exists aunique polyhedron (up to a translation or atranslation with a symmetry) realizing this metric.

• Polynomials for its volume: Sabitov 1998.
• Constructive proof: Bobenko, Izmestiev 2008.
• Poly-time algorithm: Kane, et al. 2009,…which runs in O(n456.5) time.
⇒Our problem is a special case in the framework

Observation 1
Origami Problem 1:
Input: A triangle with petals
Question: Does it fold to triangular pyramid?
Answer: “Yes” if edges match, and “long enough”…When it has a positive volume by Sabitov’spolynomial!!

Observation 2
Origami Problem 2:
Input: An quadrilateral with petals
Question: Does it fold to quadrangular pyramid?
Obs: We can obtain two triangular pyramids if we split
along one of two diagonals
1. They have the same volume in 2 ways: Pyramid!!
2. They have different volumes: One is convex and theother is concave.
3. (Sometimes we have only convex one)

4.

It seems to be difficult to go further by only Sabitov…

Crucial Observation• When you fold a petal alongan edge of the base, thelocus of the vertex follows
the perpendicular of theedge of the base, and reachto “the other side”⇒We can compute theloci of the vertices when
you fold a pyramid (withthe flat base)(Bumpy) pyramid folding problem
Problem 1:
Input: A convex n-gon with petals
Question: Does it fold to n-gonal pyramid?
[Ans] YES iff all perpendiculars meet at one point,
which corresponds to the apex.
(+each vertex has enough height)
It can be computed in linear time.
Hereafter, we consider the general case,i.e., the base should be “bumpy”

Case study: n=4(1) Petals are too short, so no pyramid cannot be folded(2) Petals are bit short, so only one convex bumpy pyramid
can be folded(3) Petals are enough long, so one convex bumpy pyramid
and another concave one can be folded

(Bumpy) pyramid folding problem
Problem 2:
Input: A convex n-gon with petals
Assumption: It cannot fold to n-gonal pyramid

Q2-1: Does it fold to convex polyhedron?
Q2-2: find polyhedron with max. volume.
[Ans] Poly-time solvable.
Simple DP: O(n3)MetaQ2-1: Two answers of Q2-1 and Q2-2 are different?
[Ans] Yes. Concave can bigger than convex!
MetaQ2-2: When? …Don’t know…

(Bumpy) pyramid folding problem
Input: A convex n-gon with petals
Q2-1: it folds to convex polyhedron?
[Theorem] (If petals are sufficiently long,)
1. Always “YES”
2. Folding way (order of gluing petals)
can be computed in linear time[Core idea of proof]
The folding way corresponds to thePower Diagram (generalized Voronoi diagram)!

Power Diagram• Voronoi Diagram:perpendicular bisector
for each pair of points• Power Diagram:

Each vertex has its own“weight”=“power”

Note：When points are convex, thediagram forms a tree, or acyclic.
http://pages.cpsc.ucalgary.ca/~laneb/Power/

(Bumpy) pyramid folding problem
Input: A convex n-gon with petals
Q2-1: it folds to convex polyhedron?
[Theorem] Always “YES”[Core idea of proof]
The folding way can be computed byusing Power Diagram
1. Each pi of the base is “point”
2. Each li is “weight/power”
3. Power Diagram (or tree) gives
the loci of ci and new generatedvertices!

Summary & Future work
Input: A convex n-gon with petals
Q1: Does it fold to n-gonal pyramid?
[Ans] Solvable in linear time.

In general, …
Q2-1: Does it fold to convex polyhedron?
[Ans] Always “YES”, and folding way can befound in linear time.
Q2-2: find polyhedron with max. volume.
[Ans] O(n3) time DP algorithm.

Summary & Future work
Input: A convex n-gon with petals
MetaQ2-1: Two answers of Q2-1 and Q2-2 aredifferent?
[Ans] Yes. Concave can bigger than convex!
MetaQ2-2: When?
…Don’t know…