CAREER: Algorithmic Semi-Algebraic Geometry and Its Applications

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

0133597 Saugata Basu Georgia Tech CAREER: Algorithmic Semi-algebraic Geometry and its Applications Algorithmic semi-algebraic geometry lies at the heart of 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. The first goal of this project is to design optimal algorithms for several important problems of semi-algebraic geometry including the problems of computing the homology groups and stratifications of semi-algebraic sets. Secondly, the methods and techniques of algorithmic real algebraic geometry will be applied to investigate several open problems in discrete and computational geometry and to explore new connections, especially in the area of computational topology. At the same time, several emerging applications of algorithmic semi-algebraic geometry will be investigated, especially in the area of constraint databases. Additionally, practical implementations will be undertaken, in order 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. This will aim at bridging the current gap between the theoretically best algorithms, and the best practical implementations available. The educational component of the project consists of developing an integrated cross-disciplinary curriculum suitable for advanced under-graduate and beginning graduate students in mathematics and computer science. This would require no pre-requisite beyond college-level calculus and linear algebra, so that that the students can quickly absorb the mathematical background necessary for this line of research, and at the same time be in a position to make efficient implementations, which would make them attractive to both industry and academia.