Global Rigidity: The Effect of Coning

• Published in: Discrete & computational geometry 2010-06, Vol.43 (4), p.717-735
• Main Authors: Connelly, R., Whiteley, W. J.
• Format: Article
• Language: English
• Subjects: Combinatorics; Computational Mathematics and Numerical Analysis; Mathematics; Mathematics and Statistics
• ISSN: 0179-5376; 1432-0444
• DOI: 10.1007/s00454-009-9220-0

Recent results have confirmed that the global rigidity of bar-and-joint frameworks on a graph G is a generic property in Euclidean spaces of all dimensions. Although it is not known if there is a deterministic algorithm that runs in polynomial time and space, to decide if a graph is generically globally rigid, there is an algorithm (Gortler et al. in Characterizing generic global rigidity, arXiv: 0710.0907v1 ,  2007 ) running in polynomial time and space that will decide with no false positives and only has false negatives with low probability. When there is a framework that is infinitesimally rigid with a stress matrix of maximal rank, we describe it as a certificate which guarantees that the graph is generically globally rigid, although this framework, itself, may not be globally rigid. We present a set of examples which clarify a number of aspects of global rigidity. There is a technique which transfers rigidity to one dimension higher: coning. Here we confirm that the cone on a graph is generically globally rigid in ℝ d +1 if and only if the graph is generically globally rigid in ℝ d . As a corollary, we see that a graph is generically globally rigid in the d -dimensional sphere if and only if it is generically globally rigid in ℝ d .