AF: Small: Algorithmic and Quantitative Semi-Algebraic Geometry and Applications

Purdue University, West Lafayette IN

Investigators

Abstract

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. Recent breakthroughs in discrete and computational geometry have spurred new research in real algebraic geometry, and there is a new synergy between these two fields. The award funds research that contributes to both areas -- increasing our understanding of real algebraic geometry, and how it impacts discrete and computational geometry. The main new ideas involved include more intricate perturbation schemes of polynomials using infinitesimals, and novel application of the well developed tool from differential topology -- namely, Morse theory, including stratified Morse theory, used in the context of semi-algebraic geometry. The results will potentially have far reaching impact in the study of arrangements in computational geometry, computer graphics, robotics, and even in areas of pure mathematics such as harmonic analysis. In addition, the research aims at developing newer and more efficient algorithms for several extremely important problems in algorithmic semi-algebraic geometry. These include algorithms for computing "roadmaps", a crucial ingredient in deciding questions of connectivity of semi-algebraic sets. These improvements will potentially impact the way the vitally important problem of robot motion planning is dealt with currently. All these research objectives are integrated in a broad program of training graduate students and curriculum development. In particular, graduate students are involved in both aspects -- namely, proving theoretical results, as well as practical implementations of algorithms.