6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2012)
[Problem Session Notes]
Polyhedron unfolding: Handles, holes, ridge trees;
sun unfolding; zipper unfolding; more ununfoldable polyhedra;
NP-completeness of edge unfolding; band unfolding;
This class covers five types of unfoldings:
The class also address a few specific questions:
- 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.
- What's the formal definition of a handle?
- Why can't unfoldings of convex polyhedra have holes?
- Why are polyhedron vertices leaves of the ridge tree?
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,