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 13 Video [previous] [next]

[+] Locked linkages: Why expansiveness, energy algorithm correctness, pointed pseudotriangulations (combinatorics, rigidity, universality, expansiveness, extremeness), linear equilateral trees can't lock, unfolding 4D chains.

This class covers several interesting results about pointed pseudotriangulations:

Their original use for polygon ray shooting data structures.
Their (fixed) number of edges and faces (in contrast to triangulations).
Their minimal generic rigidity
Every planar minimally generically rigid graph can be drawn as a pointed pseudotriangulation (a kind of universality)
Why they work as an algorithm for the Carpenter's Rule Theorem: they have expansive motions after removing a convex-hull edge. (In particular, we'll review some lemmas from CDR.)
In fact, these expansive motions are the “extreme rays” (edges) of the cone of all expansive motions.

In addition, we cover the following questions and results:

Why do we use expansiveness? Both convenience and mathematical power.
Why can't the energy algorithm get stuck in a local minimum?
New result: linear equilateral trees can't lock
Old result: 4D (and higher-dimensional) open chains can't lock

Download Video: 360p, 720p

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

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