AF: Small: Algorithmic and Quantitative Problems in Semi-algebraic and O-minimal Geometry

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

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5). The goal of the proposed research is to further our understanding of algorithmic and quantitative semi-algebraic geometry, develop new techniques especially coming from algebraic topology and the theory of o-minimal structures, and broaden the applications of semi-algebraic geometry in other areas such as discrete and computational geometry.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 proposed research will develop 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. In addition, several open problems in quantitative real algebraic geometry and closely related problems in discrete and computational geometry will be attacked with the mathematical tools developed by the PI. All these research objectives will be integrated in a broad program of training graduate students and curriculum development.