Reconfiguration and Rigidity

涉及点和各种形状的物体的几何和计算问题是理解几何建模、计算机图形学、机制分析和合成、机器人操作、结构分析、蛋白质折叠和颗粒材料的基础。 什么是几何原理，是相关的，以了解如何配置的连杆机构在平面上可以重新配置？ 什么是基本的几何工具，可以用来理解和分析面积/体积的各种安排和公式的联合和相交的圆盘在平面或空间？ 最近的进展表明，有一些微妙的和有见地的想法，可以带来对这些非常基本的问题，包括包装和覆盖问题作为极端的特殊情况。 假设给定平面或空间中的点的构型。 这些点对中的一些（但不是全部）点对之间的距离是固定的。 除了原始构形的全等复制品之外，是否存在另一个相应的构形，这些构形的点具有相同的相应距离？ 当这种情况发生时，该构型被称为全局刚性。 当配置是足够的通用，有一个合理的算法来确定它是否是全局刚性的。 例如，这在蛋白质折叠、点定位问题和结构稳定性中是有意义的。 它建议，这一理论和相应的算法可以用来提供有关分子的形状以及各种各样的新结构的稳定性的结构信息。

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.