Characterizing Generic Global Rigidity


August 23, 2007


Steven J. Gortler


Harvard University


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 Rd 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.


Steven J. Gortler

Steven (aka Shlomo) Gortler, a native of Seattle, is the Robert I. Goldman Professor of Computer Science at Harvard University. He is currently on sabbatical as a visitor to the University of Washington. Shlomo’s main area of research is computer graphics, specializing in rendering and geometry, but is often convinced to work on other things as well.