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

RUI：计算几何中伪三角剖分、可见性图和其他结构的定向拟阵和刚度理论技术

• 批准号: 0105507
• 负责人: Ileana Streinu
• 金额: $ 10.8万
• 依托单位: Smith College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2004-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105507&HistoricalAwards=false
• 关键词: RUI; Oriented; Matroids; Rigidity; Theory

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.

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