|
Published in:
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:
| AUTHOR | = | {Connelly, Robert and Jord{\'a}n, Tibor and Whiteley, Walter}, |
| TITLE | = | {Generic global rigidity of body-bar frameworks}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2009}, |
| NUMBER | = | {TR-2009-13} |