Oriented Matroids and Rigidity Theory in Computational Geometry

Smith College, Northampton MA

Investigators

Abstract

This is a continuation of the NSF grant 0105507 (2001-2004), for the exploration of how the underlying oriented matroid structure of points and lines affects properties of a variety of partially embedded combinatorial structures arising from motion planning and visibility problems in Computational Geometry. The ultimate goal is the design of efficient algorithmic solutions for a rich collection of geometric problems, some of which do not display an a priori discrete nature and could otherwise be attacked only using techniques from continuous geometry (real algebraic geometry). The focus of this research continues to be on fundamental mathematical properties and algorithms. These problems transcend application domains, but may lead to developing models and techniques for solving problems that arise in areas of science and engineering such as graphics (visibility computations with moving objects), robotics (collision detection and motion planning among obstacles) and molecular biology (protein folding). Female undergraduate students will be engaged in all aspects of the research, as well as graduate students. The combinatorial structures being studied include pseudo triangulations, visibility graphs, floodlight illumination structures and other types of embedded graphs, with or without edge length, slope or other algebraic or semi-algebraic constraints. The pointed pseudo triangulations, which I introduced in work supported by a previous grant, led to very efficient solutions for certain motion planning questions in Computational Geometry. Significant advances have been made in the last few years on understanding their properties and applying them to other algorithmic questions. Two of the most challenging remaining questions are to extend them to three dimensions and higher, and to define them for non-generic point configurations in a way that would preserve desired rigidity theoretical properties. Equally important is to develop an understanding of their kinematic properties in ways that may lead to solutions to other folding and unfolding problems in computational geometry. New problems that emerged meanwhile address fundamental properties of points in motion subject to certain controlled motion laws, and of graphs drawn on such point sets. The emphasis is on the prediction of collisions and crossings. The plan is to employ some newly discovered properties of pseudo triangulations in the parallel redrawing model of rigidity which stand a good chance for 3d and higher dimensional generalizations. Potential applications include the design of test cases for kinetic structures and shape morphing.