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

AF：小：算法和定量半代数几何及其应用

• 批准号: 1319080
• 负责人: Saugata Basu
• 金额: $ 36.88万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-10-01 至 2017-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319080&HistoricalAwards=false
• 关键词: AF; Small; Algorithmic; Quantitative; Semi

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.

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