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

[+] Rigidity theory: Pebble algorithms, rigid component decomposition, body-and-bar framework, angular rigidity, 5-connected double bananas.
This class focuses on one main question: how exactly and why does that pebble algorithm detect Laman's condition for minimal generic rigidity? We'll start with a simpler version of the algorithm that tests whether every k vertices induce at most 2k edges, and then extend to the needed 2k − 3 condition. Then I'll mention several extensions: Decomposing any graph into minimally rigid components and redundant edges Body and bar (and hinge) frameworks Angular constraints between lines and planes, or between bodies Finally, we'll see that the tricky 3D double bananas example, and indeed any graph in 3D, can be extended to be 5-connected while preserving Laman and generic flexibility.

Download Video: 360p, 720p

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

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