Analyzing rigidity with pebble games
|Authors:||Audrey Lee, Ileana Streinu, and Louis Theran|
|Proc. of:||ACM Symposium on Computational Geometry SoCG’08 Videos, 2008.|
|Full text:||DOI • URL|
How many pair-wise distances must be prescribed between an unknown set of points, and how should they be distributed, to determine only a discrete set of possible solutions? These questions, and related generalizations, are central in a variety of applications. Combinatorial rigidity shows that in two-dimensions one can get the answer, generically, via an efficiently testable sparse graph property.
We present a video and a web site illustrating algorithmic results for a variety of rigidity-related problems, as well as abstract generalizations. Our accompanying interactive software is based on a comprehensive implementation of the pebble game paradigm.