Ileana Streinu, Smith College

On Rigidity, Flexibility and Motion

Linkages are structures built from rigid (fixed lengths) bars connected by rotatable joints. Their study goes back to the peak of the Industrial Revolution in the 19th century. They have re-emerged in full strength in recent years motivated by problems from robotics, molecular biology (protein folding and protein structure determination), recreational mathematics (origami) or just simple-to-state but puzzling questions that even the men-in-the-street can understand. Here's one, the so-called Carpenter's Rule Problem: can every non-crossing planar polygonal chain be continuously reconfigured to any another position, while maintaining its edge lengths and avoiding collisions all throughout?

The (far-from-trivial) answer turned out to be YES, triggering the next question: HOW? How to perform, algorithmically, such a reconfiguring motion? I will briefly talk about my solution, based on techniques from rigidity theory, linear optimization, basic algebraic geometry, and insights from oriented matroid theory. Along the way, we will meet a new species of planar embedded graphs called pseudo-triangulations, which shift the focus from the real algebraic (and semi-algebraic) aspects of the problem to the combinatorics of rigidity, flexibility and motion. If time allows, I will include in my talk snapshots of recent work on 3- and higher-dimensional combinatorial rigidity (a still unsolved 140 year old problem going back to James C. Maxwell), and conclude with sparsity matroids and pebble game algorithms.

Back to the VGS page.