Computational Ridgidity and Motion Planning

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

The investigator continues work on the Kneser-PoulsenConjecture that was started with Professor Karoly Bezdek. Thisconjecture says that if any finite collection of disks in theEuclidean plane is rearranged so that the distance between anypair of centers does not increase, then the area of the uniondoes not increase and the area of the interesection does notdecrease. They have solved the conjecture in the plane, but manyhigher-dimensional questions remain. For example, there is acandidate for a configuration that might be a counterexample forthe analogous statement in three-space, and there are someinteresting possible differences between the case for a union ofdisks and the intersection of disks. Another major topic is thestudy of linkages in the plane that are locked in the sense thatthey can only move a small amount without crossing. The theoryof frameworks and tensegrities plays an important role here andcan be applied to give reasonable criteria to detect when such alinkage is locked. This is continuing work of the investigator,Erik Demaine, and Gunter Rote, who originally solved thecarpenter's rule problem, which states that any polygonal arc canbe opened without creating any self-intersection. The investigator works on certain basic, fundamentalquestions about the geometry of discrete objects. Just asphysics asks fundamental questions about the nature of matter,space, and the universe, and the physical laws they must obey,geometry asks fundamental questions about how geometric objectsinteract and the implicit constraints they satisfy. How does thearea of the union of round disks change as the centers are movedapart? The investigator (with Karoly Bezdek) has shown that thearea behaves (it increases or stays the same) as expected in theplane, but the situation in space is not so clear. When is arobot arm in the plane rigid, and when can it be opened? Theinvestigator (with Erik Demaine and Gunter Rote) has shown thatarms open as expected in the plane, but what about morecomplicated linkages? What can be said about the rigidity ofpackings of round balls as a granular material? The investigatoris an expert in such matters, but there are delicate questionsabout the rigidity in a container with a small number of disks.The volume enclosed by a flexible surface is constant, but whatabout other geometric invariants? These are concrete tangibleobjects, but accessible to the appropriate geometric insight.These questions are both relevant and potentially quite usefulfor subjects as wide-ranging as cell biology, protein folding,kinematics, and granular materials. For example, it is widelybelieved that the geometric structure of a cell has a great dealto do with its function. So the rigidity of appropriate discreteobjects is relevant. As has been shown over and over again inphysics and mathematics, if the questions are to the point,applications follow.