/

Characterizing Generic Global Rigidity

Steven J. Gortler, Alexander D. Healy, Dylan P. Thurston
Arxiv ID: 0710.0926Last updated: 10/13/2021
A d-dimensional framework is a graph and a map from its vertices to E^d. Such a framework is globally rigid if it is the only framework in E^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: a generic framework is globally rigid if and only if it has a stress matrix with kernel of dimension d+1, the minimum possible. An alternate version of the condition comes from considering the geometry of the length-squared mapping l: the graph is generically locally rigid iff the rank of l is maximal, and it is generically globally rigid iff the rank of the Gauss map on the image of l is maximal. We also show that this condition is efficiently checkable with a randomized algorithm, and prove that if a graph is not generically globally rigid then it is flexible one dimension higher.

PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.

Related papers

About
Pricing
Commercial Disclosure
Contact
© 2023 Paper Studio™. All Rights Reserved.