Oriented Matroids and Rigidity Theory in Computational Geometry

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

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.