Computational Ridgidity and Motion Planning

Cornell University, Ithaca NY

Investigators

Abstract

The investigator continues work on the Kneser-Poulsen Conjecture that was started with Professor Karoly Bezdek. This conjecture says that if any finite collection of disks in the Euclidean plane is rearranged so that the distance between any pair of centers does not increase, then the area of the union does not increase and the area of the interesection does not decrease. They have solved the conjecture in the plane, but many higher-dimensional questions remain. For example, there is a candidate for a configuration that might be a counterexample for the analogous statement in three-space, and there are some interesting possible differences between the case for a union of disks and the intersection of disks. Another major topic is the study of linkages in the plane that are locked in the sense that they can only move a small amount without crossing. The theory of frameworks and tensegrities plays an important role here and can be applied to give reasonable criteria to detect when such a linkage is locked. This is continuing work of the investigator, Erik Demaine, and Gunter Rote, who originally solved the carpenter's rule problem, which states that any polygonal arc can be opened without creating any self-intersection. The investigator works on certain basic, fundamental questions about the geometry of discrete objects. Just as physics 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 objects interact and the implicit constraints they satisfy. How does the area of the union of round disks change as the centers are moved apart? The investigator (with Karoly Bezdek) has shown that the area behaves (it increases or stays the same) as expected in the plane, but the situation in space is not so clear. When is a robot arm in the plane rigid, and when can it be opened? The investigator (with Erik Demaine and Gunter Rote) has shown that arms open as expected in the plane, but what about more complicated linkages? What can be said about the rigidity of packings of round balls as a granular material? The investigator is an expert in such matters, but there are delicate questions about the rigidity in a container with a small number of disks. The volume enclosed by a flexible surface is constant, but what about other geometric invariants? These are concrete tangible objects, but accessible to the appropriate geometric insight. These questions are both relevant and potentially quite useful for subjects as wide-ranging as cell biology, protein folding, kinematics, and granular materials. For example, it is widely believed that the geometric structure of a cell has a great deal to do with its function. So the rigidity of appropriate discrete objects is relevant. As has been shown over and over again in physics and mathematics, if the questions are to the point, applications follow.