From infinitesimal to global rigidity

Robert Connelly

Cornell University

April 21,
refreshments at 3:45pm


Suppose that a finite set of labeled points in the plane, a configuration, is given. Some pairs of those points, determined by a finite simple graph G, are to be kept at their same fixed distance apart. If the coordinates of the configuration are generic, then the question of whether the configuration is rigid is a purely combinatorial property of G, for which there isa polynomial-time algorithm. (A configuration is generic if there is no non-trivial integral polynomial satisfied by the coordinates.) But rigidity is a local property equivalent to there being only trivial infinitesimal motions satisfying the distance constraints. Is it possible to determine the more basic question as to whether there is any other non-congruent configuration in the planethat satisfies the distance constraints? If the distance constraints determine the configuration up to congruence, the configuration is called globally rigid, and if the configuration is assumed to be generic, the graph G is called generically globally rigid (in the plane). Necessary conditions for generic global rigidity in the plane are generic rigidity even when any edge is removed from G (generic redundant rigidity), It turns out that these conditions are also sufficient, which were conjectured by B. Hendrickson some years ago. The proof of this involves the calculation of the rank of a matrix (what I call a stress matrix), and a construction, due to T. Jordan and W. Sullivan, that builds G starting from the complete graph K(4) by operations that preserve the properties of being vertex 3-connected and generic redundant rigidity. and that G should be vertex 3-connected.

Speaker's Contact Info: connelly(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on March 31, 2004 at 03:51 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.