Generic global rigidity in three dimensions
From Egres Open
Decide whether a graph is globally rigid in three-dimensional space.
Remarks
In a paper by Gortler, Healy, and Thurston [1], it is shown that global rigidity of a generic framework depends only on the graph, so global rigidity of graphs can be defined in any dimension. Furthermore, they show that global rigidity of a graph can be determined by computing the rank of a matrix of indeterminates, thus there is a randomized polynomial algorithm. Jackson, McCourt, and Nixon [2] give necessary conditions for global rigidity on various surfaces, and propose a conjecture that would imply a polynomial algorithm for generic global rigidity on a cylinder or a cone.
References
- ↑ S. J. Gortler, A. D. Healy, D. P. Thurston, Characterizing Generic Global Rigidity, DOI link, arXiv link
- ↑ B. Jackson, T. McCourt, A. Nixon, Necessary Conditions for the Generic Global Rigidity of Frameworks on Surfaces, DOI link, arXiv link
