RUI: Oriented Matroids and Rigidity Theory Techniques for Pseudo Triangulations, Visibility Graphs and Other Structures in Computational Geometry

Smith College, Northampton MA

Investigators

Abstract

RUI: Oriented Matroids and Rigidity Theory Techniques for Pseudo Triangulations, Visibility Graphs and Other Structures in Computational Geometry PI: Ileana Streinu Abstract: This research is motivated by fundamental questions in Robotics and Computer Graphics, such as planning the motion of a robot arm, detecting collisions and computing visibilities. It seeks efficient algorithmic solutions by investigating the underlying computational structures with novel mathematical tools and it has a substantial potential to lead to applications in understanding the nature of the protein folding process in biology. The investigator is undertaking a systematic plan of research aimed at furthering the understanding of how the underlying oriented matroid structure of points and lines affects properties of a variety of partially embedded combinatorial structures such as pseudo triangulations and visibility graphs. The focus is on combinatorial (enumeration, generation, characterization) and algorithmic questions, the underlying framework is geometric (dimensions 2 and 3), and the techniques involved come from matroid and oriented matroid theory, rigidity theory, combinatorial topology, computational algebraic geometry and graph embeddings.