Reconfiguration and Rigidity

Cornell University, Ithaca NY

Investigators

Abstract

Geometric and computational problems involving points and objects of various shapes are basic to the understanding of geometric modeling, computer graphics, the analysis and synthesis of mechanisms, robot manipulation, structural analysis, protein folding and granular materials, for example. What are the geometric principles that are relevant to understanding how configurations of linkages in the plane can be reconfigured? What are the basic geometric tools that can be applied to understand and analyze the area/volume of various arrangements and formulas for the union and intersections of circular disks in the plane or space? Recent advances have shown that there are some subtle and insightful ideas that can be brought to bear on these very basic problems that include packing and covering problems as extreme special cases. Suppose a configuration of points in the plane or space is given. The distance between some (but not all) of the pairs of these points is fixed. Is there another corresponding configuration, other than congruent copies of the original configuration, of the points with corresponding distances the same? When this occurs, the configuration is called globally rigid. When the configuration is sufficiently generic, there is a reasonable algorithm to determine if it is globally rigid. This is of interest in protein folding, point location problems and structural stability, for example. It is proposed that this theory and corresponding algorithms can be used to provide structural information about the shapes of molecules as well as the stability of a wide variety of novel structures.