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.

代数半代数几何是计算机科学和数学的几个不同领域中许多问题的核心，包括离散和计算几何，机器人运动规划，几何建模，计算机辅助设计，几何定理证明，真实的代数簇的数学研究，分子化学，约束数据库，近年来，离散几何和计算几何领域的突破，促使人们对真实的代数几何进行了新的研究，这两个领域之间产生了新的协同作用。 该奖项资助的研究，有助于这两个领域-增加我们的理解真实的代数几何，以及它如何影响离散和计算几何。 所涉及的主要新思想包括更复杂的扰动计划的多项式使用无穷小，和新的应用程序的发达工具从微分拓扑学-即莫尔斯理论，包括分层的莫尔斯理论，在半代数几何的背景下使用。 这些结果可能会对计算几何、计算机图形学、机器人技术甚至纯数学领域（如调和分析）的安排研究产生深远的影响。此外，本研究的目的是为算法半代数几何中的几个极其重要的问题开发更新和更有效的算法。 这些算法包括计算“路线图”，在决定问题的连通性的半代数集的一个重要组成部分。 这些改进将潜在地影响机器人运动规划这一至关重要的问题的处理方式。 所有这些研究目标都整合在培养研究生和课程开发的广泛计划中。特别是，研究生参与这两个方面-即，证明理论结果，以及算法的实际实现。