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

Prof. Erik Demaine       TA: Jayson Lynch


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

Class 20 Video     [previous] [next]

[+] 3D linkage folding: ribosomes, HP protein folding NP-hardness, flattening is strongly NP-hard, flips, flipturns, deflations, pops, popturns.
This class covers both L19 and L21.

This class opens with a discussion about the class as a whole, and how the experimental split into video lectures + live classes worked out.

Second, we address a few questions concerning:

  • Equilateral vs. equiangular vs. obtuse locked 3D chains
  • The shape of the ribosome
  • HP protein folding NP-hardness proofs

Third, we cover a new result: Flattening fixed angle chains (and min/max flat span) are strongly NP-hard [Demaine & Eisenstat 2011].

Fourth, we cover a fun series of results on polygon (closed chain) reconfiguration via flips, flipturns, deflations, pops, and popturns. [More detail can be found in 2010's Lecture 21.]

Download Video: 360p, 720p

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

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

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

Plots by Erik using matplotlib

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