Design and Implementation of Algorithms in Semi-Algebraic Geometry

点击翻译按钮获取中文摘要

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.