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

Prof. Erik Demaine

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

Lecture 15 Video     [previous] [next]

[+] Polyhedron folding: Decision problem, enumeration problem, combinatorial problem, nonconvex solution, convex polyhedral metrics, Alexandrov gluings, Alexandrov's Theorem, Bobenko-Izmestiev constructive proof, pseudopolynomial algorithm, ungluable polygons, perimeter halving, gluing tree, rolling belts.

This lecture dives into the problem of folding polygons into polyhedra. The focus here is on folding convex polyhedra, though there is one nice result about the nonconvex case by Burago & Zalgaller.

The main tool in this area is called Alexandrov's Theorem, from 1941, which characterizes when a gluing of the boundary of a polygon will result in a convex polyhedron; plus, as we saw last lecture, that convex result is always unique. We'll sketch a proof of this theorem as well as recent algorithms for finding the convex polyhedron.

With this tool in hand, we'll explore some different properties of gluings. Some polygons, in fact "most" in a certain sense, have no Alexandrov gluings. Convex polygons, on the other hand, always do. Some polygons have infinitely many gluings, but this always happens in a controlled way with a few "rolling belts". Along the way we'll see gluing trees, a useful tool for analyzing gluings that we'll use in the next lecture for algorithms to find gluings.

Download Video: 360p, 720p

Handwritten notes, page 1/8[previous page][next page][PDF]

Handwritten notes, page 1/8[previous page][next page][PDF]

Slides, page 1/2[previous page][next page][PDF]

Figure 23.10 of GFALOP

Slides, page 1/2[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.