Oriented Matroids and Rigidity Theory in Computational Geometry

计算几何中的定向拟阵和刚性理论

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

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.

这是美国国家科学基金会资助0105507（2001-2004）的延续，用于探索点和线的基本定向拟阵结构如何影响计算几何中运动规划和可见性问题所产生的各种部分嵌入组合结构的属性。最终目标是设计有效的算法解决方案的几何问题，其中一些不显示先验离散性质，否则只能使用连续几何（真实的代数几何）的技术攻击。这项研究的重点仍然是基本的数学性质和算法。这些问题超越了应用领域，但可能会导致开发模型和技术来解决科学和工程领域出现的问题，如图形（移动物体的可见性计算），机器人（障碍物之间的碰撞检测和运动规划）和分子生物学（蛋白质折叠）。女本科生将从事研究的各个方面，以及研究生。正在研究的组合结构包括伪三角剖分，可见性图，泛光灯照明结构和其他类型的嵌入式图，有或没有边长，斜率或其他代数或半代数约束。指出伪三角，我介绍了在工作中支持以前的补助金，导致了非常有效的解决方案，某些运动规划问题的计算几何。 在过去的几年里，在理解它们的性质并将其应用于其他算法问题方面取得了重大进展。剩下的两个最具挑战性的问题是将它们扩展到三维或更高的空间，并以一种保持所需刚性理论性质的方式定义它们为非通用点配置。同样重要的是发展的方式，可能会导致解决其他折叠和展开问题的计算几何的运动学性质的理解。新出现的问题，同时解决的基本性质的点在运动中受到某些控制的运动规律，并绘制在这样的点集的图形。重点是预测碰撞和交叉。 该计划是采用一些新发现的性质的伪三角形的平行重绘模型的刚性，这是一个很好的机会，三维和更高维的推广。潜在的应用包括动力学结构和形状变形的测试用例的设计。