Characterizing Generic Global Rigidity
<-- Return to the list
Date: 10-16-2007
Start Time:
4:00pm
End Time: 5:00pm
Speaker: Dylan Thurston, Barnard College, Columbia Unversity
Location: 622 Math
ABSTRACT
A d-dimensional framework is a graph and a map from its vertices to єd. Such a framework is globally rigid if it is the only frameworkin єd with the same graph and edge lengths, up to rigid motions. For which underlying graphs is a generic framework globally rigid? We answer this question by proving a conjecture by Connelly, that his sufficient condition is also necessary. The condition comes from considering the geometry of the length-squared mapping ℓ; essentially, the graph is generically locally rigid iff the rank of ℓ is maximal, and it is generically globally rigid iff theran of the Gauss map on the image of ℓ is maximal. (This is an equivalent reformulation of Connelly’s version of the condition, which was in terms of the size of the kernel of a generic stress matrix.) We also show that this condition is efficiently checkable with a randomized algorithm.
This is joint work with Steven Gortler and Alex Healy.
BIO
For more informataion about Dr. Thurston, please visit this site.