AF: Small: Algorithmic and Quantitative Semi-Algebraic Geometry and Applications

算法半代数几何是计算机科学和数学几个不同领域中许多问题的核心，包括离散和计算几何、机器人运动规划、几何建模、计算机辅助设计、几何定理证明、真实代数变量的数学研究、分子化学、约束数据库等。离散几何和计算几何的最新突破刺激了实代数几何的新研究，这两个领域之间存在新的协同作用。该奖项资助对这两个领域都有贡献的研究——增加我们对真正代数几何的理解，以及它如何影响离散几何和计算几何。涉及的主要新思想包括使用无穷小的多项式的更复杂的摄动方案，以及微分拓扑中发展良好的工具的新应用-即莫尔斯理论，包括分层莫尔斯理论，在半代数几何的背景下使用。这些结果将对计算几何、计算机图形学、机器人技术，甚至是谐波分析等纯数学领域的排列研究产生深远的影响。此外，本研究旨在针对算法半代数几何中几个极其重要的问题开发更新、更有效的算法。其中包括计算“路线图”的算法，这是决定半代数集连通性问题的关键因素。这些改进将潜在地影响当前处理机器人运动规划这一至关重要的问题的方式。所有这些研究目标都整合在研究生培训和课程开发的广泛计划中。特别是，研究生涉及两个方面——即证明理论结果，以及算法的实际实现。

Algorithmic semi-algebraic geometry lies at the heart of many problems in several different areas of computer science and mathematics, including discrete and computational geometry, robot motion planning, geometric modeling, computer-aided design, geometric theorem proving, mathematical investigations of real algebraic varieties, molecular chemistry, constraint databases, etc. Recent breakthroughs in discrete and computational geometry have spurred new research in real algebraic geometry, and there is a new synergy between these two fields. The award funds research that contributes to both areas -- increasing our understanding of real algebraic geometry, and how it impacts discrete and computational geometry. The main new ideas involved include more intricate perturbation schemes of polynomials using infinitesimals, and novel application of the well developed tool from differential topology -- namely, Morse theory, including stratified Morse theory, used in the context of semi-algebraic geometry. The results will potentially have far reaching impact in the study of arrangements in computational geometry, computer graphics, robotics, and even in areas of pure mathematics such as harmonic analysis. In addition, the research aims at developing newer and more efficient algorithms for several extremely important problems in algorithmic semi-algebraic geometry. These include algorithms for computing "roadmaps", a crucial ingredient in deciding questions of connectivity of semi-algebraic sets. These improvements will potentially impact the way the vitally important problem of robot motion planning is dealt with currently. All these research objectives are integrated in a broad program of training graduate students and curriculum development. In particular, graduate students are involved in both aspects -- namely, proving theoretical results, as well as practical implementations of algorithms.