AF: Small: Algorithmic and Quantitative Problems in Semi-algebraic and O-minimal Geometry

AF：小：半代数和 O 最小几何中的算法和定量问题

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

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The goal of the proposed research is to further our understanding of algorithmic and quantitative semi-algebraic geometry, develop new techniques especially coming from algebraic topology and the theory of o-minimal structures, and broaden the applications of semi-algebraic geometry in other areas such as discrete and computational geometry.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. A closely related subject area is quantitative real algebraic geometry. Results from quantitative real algebraic geometry are the basic ingredients of better algorithms in semi-algebraic geometry and play an increasingly important role in several other areas of computer science: for instance, in bounding the geometric complexity of arrangements in computational geometry, computational learning theory, proving lower bounds in computational complexity theory, convex optimization problems, etc. As such, algorithmic and quantitative real-algebraic geometry has been an extremely active area of research in recent years.The proposed research will develop new techniques in real algebraic geometry that would lead to new and better algorithms, for computing topological invariants of semi-algebraic sets in theory, as well as practice. In addition, several open problems in quantitative real algebraic geometry and closely related problems in discrete and computational geometry will be attacked with the mathematical tools developed by the PI. All these research objectives will be integrated in a broad program of training graduate students and curriculum development.

该奖项根据 2009 年美国复苏和再投资法案（公法 111-5）提供资金。本研究的目的是加深我们对算法和定量半代数几何的理解，开发新技术，特别是来自代数拓扑和 o-最小结构理论的新技术，并扩大半代数几何在其他领域的应用，例如算法半代数几何是计算机科学和数学几个不同领域中许多问题的核心，包括离散和计算几何、机器人运动规划、几何建模、计算机辅助设计、几何定理证明、实代数簇的数学研究、分子化学、约束数据库等。一个密切相关的学科领域是定量实代数几何。定量实代数几何的结果是半代数几何中更好算法的基本成分，并且在计算机科学的其他几个领域中发挥着越来越重要的作用：例如，在限制计算几何排列的几何复杂性、计算学习理论、证明计算复杂性理论、凸优化问题等的下界。因此，算法和定量实代数几何近年来一直是一个非常活跃的研究领域。所提出的研究将开发实代数几何中的新技术，这将导致到新的更好的算法，用于在理论和实践中计算半代数集的拓扑不变量。此外，PI开发的数学工具将解决定量实代数几何中的几个开放问题以及离散和计算几何中密切相关的问题。所有这些研究目标将整合到研究生培训和课程开发的广泛计划中。