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

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

RUI: Oriented Matroids and Rigidity Theory Techniques for PseudoTriangulations, Visibility Graphs and Other Structures in ComputationalGeometryPI: Ileana StreinuAbstract:This research is motivated by fundamental questions in Robotics andComputer Graphics, such as planning the motion of a robot arm, detectingcollisions and computing visibilities. It seeks efficient algorithmicsolutions by investigating the underlying computational structures withnovel mathematical tools and it has a substantial potential to lead toapplications in understanding the nature of the protein folding process inbiology.The investigator is undertaking a systematic plan of research aimed atfurthering the understanding of how the underlying oriented matroidstructure of points and lines affects properties of a variety of partiallyembedded combinatorial structures such as pseudo triangulations andvisibility graphs. The focus is on combinatorial (enumeration, generation,characterization) and algorithmic questions, the underlying framework isgeometric (dimensions 2 and 3), and the techniques involved come frommatroid and oriented matroid theory, rigidity theory, combinatorialtopology, computational algebraic geometry and graph embeddings.