Rigidity, Flexibility, Stress and Motion: Foundations of Reconfiguration Problems in Computational Geometry

点击翻译按钮获取中文摘要

Reconfiguration problems underlie modern mathematical investigations in robotics, mechanical design, structural engineering, and bio-geometry, and have the potential of impacting computational biology, especially the problems emerging from modeling protein folding or, more generally, protein flexibility and motion.This research is focused on fundamental mathematical properties and algorithms for reconfiguration problems (in particular, motion planning) of linkages and other flexible structures made from rigid parts connected together with various types of joints and hinges. The research builds upon the principal investigator's previous work on 2-dimensional robot arm reconfiguration (the Carpenter's Rule problem and pointed pseudo-triangulations), as well as on her current work in Combinatorial Rigidity (generalizations of Pebble Game algorithms for 2-dimensional-rigidity to other classes of sparse graphs, computation of rigid and stressed clusters) and Motion generation (for pseudo-triangulations in the plane, and for molecular structures with many loops in 3-dimensions). The goal of this research is furthering the general understanding of a notorious 140-old open problem in the Combinatorial Rigidity of bar-and-joint frameworks, expansive motions and pseudo-triangulations in 3-dimensions, as well as motion and reconfiguration for other 3d-structures (linkages, panel-and-hinge and polyhedral structures). These problems transcend application domains, but they are motivated by and may lead to developing models and techniques for addressing questions that arise in other areas of science and engineering.