Description:
Consider a graph embedded in D-dimensional Euclidian space, with edges drawn as straight lines. We say that this embedding of the graph is globally rigid if it there is no other embedding of the graph in R^d with the same edge lengths. Testing for global rigidity is in general NP-hard.
In this talk, I will describe a simple way to characterize global rigidity under the (mild) assumption that the embedding is "generic". In particular, we prove that Connelly's sufficient condition for generic global rigidity is also necessary. This condition can be tested efficiently using a randomized algorithm.
The global rigidity test uses the concept of an equillibrium stress matrix, a notion that also appears in mesh pamameterization and nonlinear dimensionality reduction.
Global rigidity may have implications in chemistry and sensor networks.
This is joint work with Alex Healy and Dylan Thurston.
Speaker(s):
Steven J. Gortler, Professor, Computer Science, Harvard University
|
