Algorithmic Problems in Semi-algebraic Geometry and Topology

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

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.