Algorithmic Problems in Semi-algebraic Geometry and Topology

半代数几何和拓扑中的算法问题

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

Number: 0634907Institution: Georgia Tech Research Corporation - GA Institute of TechnologyPI: Basu, Saugata Title: Algorithmic Problems in Semi-algebraic Geometry and TopologyAbstract: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 main research objectives would include, development of 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, and bringing methods and techniques of algorithmic real algebraic geometry to bear on several open problems in discrete and computational geometry and to explore new connections, especially in the area of computational topology. The educational goals involve, developing an integrated cross-disciplinary curriculum suitable for advanced under-graduate and beginning graduate students, requiring no pre-requisite beyond college-level calculus and linear algebra, so that that they can quickly absorb the mathematical background necessary for this line of research. The broader impact of the proposed activity would include training of new graduate students in the field of algorithmic semi-algebraic geometry, as well as collaborative research spanning several different areas: real algebraic geometry, discrete and computational geometry, symbolic computation and computational complexity theory.

编号：0634907 机构：佐治亚理工学院研究公司 - GA 理工学院 PI：Basu，Saugata 标题：半代数几何和拓扑中的算法问题 摘要：算法半代数几何是计算机科学和数学几个不同领域中许多问题的核心包括离散几何和计算几何、机器人运动规划、几何建模、计算机辅助设计、几何定理证明、实际数学研究代数簇、分子化学、约束数据库等。一个密切相关的学科领域是定量实代数几何。定量实代数几何的结果是半代数几何中更好算法的基本成分，并且在计算机科学的其他几个领域中发挥着越来越重要的作用：例如，在限制计算几何排列的几何复杂性、计算学习理论、证明计算复杂性理论、凸优化问题等的下限。因此，算法和定量实代数几何近年来一直是一个非常活跃的研究领域。主要研究目标包括，开发实代数几何新技术，会带来新的更好的算法，用于在理论和实践中计算半代数集的拓扑不变量，并将算法实代数几何的方法和技术应用于离散几何和计算几何中的几个开放问题，并探索新的联系，特别是在计算拓扑领域。教育目标包括开发适合高年级本科生和初级研究生的综合跨学科课程，除了大学水平的微积分和线性代数之外不需要任何先决条件，以便他们能够快速吸收所需的数学背景研究线。拟议活动的更广泛影响将包括在算法半代数几何领域对新研究生进行培训，以及跨越几个不同领域的合作研究：实代数几何、离散和计算几何、符号计算和计算复杂性理论。