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

摘要：本研究的动机是机器人技术和计算机图形学的基本问题，如规划机械手臂的运动、检测碰撞和计算可见性。它通过使用新颖的数学工具研究潜在的计算结构来寻求有效的算法解决方案，并且它在理解生物学中蛋白质折叠过程的本质方面具有巨大的应用潜力。研究者正在进行一项系统的研究计划，旨在进一步了解点和线的潜在定向矩阵结构如何影响各种部分嵌入组合结构（如伪三角测量和可见性图）的特性。重点是组合（枚举，生成，表征）和算法问题，基本框架是几何的（维度2和3），涉及的技术来自矩阵和定向矩阵理论，刚性理论，组合拓扑，计算代数几何和图嵌入。

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.