Generic global rigidity of body-hinge frameworks

摘要

A d-dimensional body-hinge framework is a structure consisting of rigid bodies in d-space in which some pairs of bodies are connected by a hinge, restricting the relative position of the corresponding bodies. The framework is said to be globally rigid if every other arrangement of the bodies and their hinges can be obtained by a congruence of the space. The combinatorial structure of a body-hinge framework can be encoded by a multigraph H, in which the vertices correspond to the bodies and the edges correspond to the hinges. We prove that a generic body-hinge realization of a multigraph H is globally rigid in R-d, d >= 3, if and only if (((d+1)(2)) 1)H - e contains ((d+1)(2)) edge-disjoint spanning trees for all edges e of (((d+1)(2)) 1)H. (For a multigraph H and integer k we use kH to denote the multigraph obtained from H by replacing each edge e of H by k parallel copies of e.) This implies an affirmative answer to a conjecture of Connelly, Whiteley, and the first author.