Algorithmic Problems in Semi-algebraic Geometry and Topology

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

Number: 0634907Institution: Georgia Tech Research Corporation - GA Institute of TechnologyPI: Basu, Saugata Title: Algorithmic Problems in Semi-algebraic Geometry and TopologyAbstract: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 main research objectives would include, development of 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, and bringing methods and techniques of algorithmic real algebraic geometry to bear on several open problems in discrete and computational geometry and to explore new connections, especially in the area of computational topology. The educational goals involve, developing an integrated cross-disciplinary curriculum suitable for advanced under-graduate and beginning graduate students, requiring no pre-requisite beyond college-level calculus and linear algebra, so that that they can quickly absorb the mathematical background necessary for this line of research. The broader impact of the proposed activity would include training of new graduate students in the field of algorithmic semi-algebraic geometry, as well as collaborative research spanning several different areas: real algebraic geometry, discrete and computational geometry, symbolic computation and computational complexity theory.