6.849: Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Fall 2012)
[Problem Session Notes]
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
- 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
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,