TR-2009-13

Generic global rigidity of body-bar frameworks

Robert Connelly, Tibor Jordán, Walter Whiteley

Published in:
J. Combinatorial Theory, Ser. B., Vol. 103, Issue 6, November 2013, pp. 689-705.



Abstract

A basic geometric question is to determine when a given framework G(p) is globally rigid in Euclidean space Rd, where G is a finite graph and p is a configuration of points corresponding to the vertices of G. G(p) is globally rigid in Rd if for any other configuration q for G such that the edge lengths of G(q) are the same as the corresponding edge lengths of G(p), then p is congruent to q. A framework G(p) is redundantly rigid, if it is rigid and it remains rigid after the removal of any edge of G. Hendrickson [9] proved that redundant rigidity is a necessary condition for generic global rigidity, as is (d + 1)-connectivity.
 
Recent results in [2] and [10] have shown that when the configuration p is generic and d=2, redundant rigidity and 3-connectivity are also sufficient - a good combinatorial characterization that only depends on G and can be checked in polynomial time. It appears that a similar result for d=3 is beyond the scope of present techniques and there are counterexamples to the sufficiency of Hendrickson's conditions.
 
However, there is a special class of generic frameworks that have polynomial time algorithms for their generic rigidity (and redundant rigidity) in Rd for any d, as shown in [19], namely generic body-and-bar frameworks. Such frameworks are constructed from a finite number of rigid bodies that are connected by bars generically placed with respect to each body. We show that a body-and-bar framework is generically globally rigid in Rd, for any d, if it is redundantly rigid. As a consequence there is a deterministic polynomial time combinatorial algorithm on the graph to determine the generic global rigidity of body-and-bar frameworks in any dimension.


Bibtex entry:

@techreport{egres-09-13,
AUTHOR = {Connelly, Robert and Jord{\'a}n, Tibor and Whiteley, Walter},
TITLE = {Generic global rigidity of body-bar frameworks},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-13}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!