6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2012)

Prof. Erik Demaine TA: Jayson Lynch

[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Accessibility]

Class 15 Video [previous] [next]

[+] Polyhedron unfolding: Handles, holes, ridge trees; sun unfolding; zipper unfolding; more ununfoldable polyhedra; NP-completeness of edge unfolding; band unfolding; continuous blooming.

This class covers five types of unfoldings:

Sun unfolding: A new generalization of the source unfolding that also incorporates elements of the star unfolding. It provably doesn't overlap. (Non)overlap of a dual version, which generalizes the star unfolding, remains an open problem.
Zipper unfolding: A new type of unfolding where the cutting forms a path. We have several specific examples and counterexamples of zipper edge unfoldings, but it remains open whether all convex polyhedra have general zipper unfoldings.
Edge-ununfoldability: We show several other edge-ununfoldable examples, the smallest of which has 13 faces, which is conjectured optimal. More generally, deciding whether a topologically convex orthogonal polyhedron has an edge unfolding is NP-complete. Pepakura's brute-force heuristics do decently in practice.
Band unfolding: A brief overview of how the side band of a prismatoid unfolds (even continuously blooms) without overlap. Attaching the top and bottom faces remains an open problem.
Continuous blooming: We cover two ways to continuously unfold any convex polyhedra. First, any unfolding can be refined and then bloomed, by making its dual Hamiltonian and sequentially unrolling. Second, the source unfolding blooms as is, by following a postorder traversal. Many open problems remain.

The class also address a few specific questions:

What's the formal definition of a handle?
Why can't unfoldings of convex polyhedra have holes? (Gauss-Bonnet Theorem)
Why are polyhedron vertices leaves of the ridge tree?

Download Video: 360p, 720p

Handwritten notes, page 1/6 • [previous page] • [next page] • [PDF]

Slides, page 1/37 • [previous page] • [next page] • [PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.