Design and Implementation of Algorithms in Semi-Algebraic Geometry

由于算法半代数几何在机器人运动规划、几何建模、计算机辅助设计、几何定理证明、实代数簇的数学研究、离散几何和计算几何以及分子化学等领域的应用，近年来引起了人们的广泛关注。本研究项目涉及半代数几何中的几个核心算法问题，研究的理论领域包括半代数几何中的各种算法问题，它们与离散几何和计算几何中几个重要问题的联系，以及算法半代数几何在约束数据库和控制理论等领域的新应用。其实际目标是建立一个能够计算给定半代数集的拓扑不变量(如连通分支数、欧拉特征、Betti数、全同调群)的系统。多项式系统求解是计算高阶拓扑不变量算法的基本步骤。功能强大的多变量多项式系统解算器最近已经出现。这些专门的系统比标准计算机代数包中提供的系统更有效。然而，没有任何努力来计算更多的几何性质，如连通分支的数量，每个连通分支的描述，同调群等。解决这些问题的算法比仅仅测试半代数集的空性的算法要复杂得多。将从现有的最先进的多项式系统解算器中采用例程作为构建块，以开发能够回答有关半代数集的连通性和更高同调的问题的软件包。

Algorithmic semi-algebraic geometry has attracted a lot of attention in recent years due to its applications in a range of areas such as robot motion planning, geometric modeling, computer-aided design, geometric theorem proving, mathematical investigations of real algebraic varieties, discrete and computational geometry, and molecular chemistry. This research project is concerned with several central algorithmic problems in semi-algebraic geometry.The theoretical areas to be investigated consist of various algorithmic problems in semi-algebraic geometry, their connections with several important problems in discrete and computational geometry, as well as new applications of algorithmic semi-algebraic geometry to such areas as constraint databases and control theory. The practical goal is to build a system able to compute topological invariants (such as the number of connected components, the Euler characteristic, the Betti numbers, the full homology groups) of given semi-algebraic sets. Polynomial system solving is a basic step in the algorithms for computing higher topological invariants. Powerful multivariate polynomial system solvers have recently become available. These specialized systems are more efficient than what is available in standard computer algebra packages. However, there has not been any effort to compute more geometric properties, like the number of connected components, descriptions of each connected component, the homology groups etc. The algorithms for solving these problems are considerably more complicated than those for just testing emptiness of a semi-algebraic set. Routines will be adopted from existing state-of-the-art polynomial system solvers as building blocks towards developing a software package able to answer questions about connectivity and higher homologies of semi-algebraic sets.