科研之友
微信
新浪微博
Facebook
分享链接
摘要
It is an intriguing open problem to give a combinatorial characterisation or polynomial algorithm for determining when a graph is globally rigid in a"e (d) . This means that any generic realisation is uniquely determined up to congruence when each edge represents a fixed length constraint. Hendrickson gave two natural necessary conditions, one involving connectivity and the other redundant rigidity. In general, these are not sufficient, but they do suffice in two dimensions, as shown by Jackson and Jordan. Our main result is an analogue of the redundant rigidity condition for frameworks that have both direction and length constraints. For any generic globally rigid direction-length framework in a"e (d) with at least 2 length edges, we show that deleting any length edge results in a rigid framework. It seems harder to obtain a corresponding result when a direction edge is deleted: we can do this in two dimensions, under an additional hypothesis that we believe to be unnecessary. Our proofs use a lemma of independent interest, stating that a certain space parameterising equivalent frameworks is a smooth manifold. We prove this lemma using arguments from differential topology and the Tarski-Seidenberg theorem on semi-algebraic sets.
- 出版日期2011-7
