Journal
DISCRETE & COMPUTATIONAL GEOMETRY
Volume 43, Issue 4, Pages 717-735Publisher
SPRINGER
DOI: 10.1007/s00454-009-9220-0
Keywords
Infinitesimal rigidity; Global rigidity; Self-stress; Coning; Projective geometry; Spherical geometry
Categories
Funding
- NSF [DMS-0209595]
- NSERC (Canada)
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [0809068] Funding Source: National Science Foundation
Ask authors/readers for more resources
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 Rd+1 if and only if the graph is generically globally rigid in R-d. As a corollary, we see that a graph is generically globally rigid in the d-dimensional sphere S-d if and only if it is generically globally rigid in R-d.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available