Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems

2007/08/21 by Basu, Saugata
#14P10 #14P25 (Primary) 68W30 (Secondary) #Algebraic Geometry (math.AG) #Algebraic Topology (math.AT) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT)

paper · doi:10.48550/arxiv.0708.2854

Abstract

We give a survey of algorithms for computing topological invariants of semi-algebraic sets with special emphasis on the more recent developments in designing algorithms for computing the Betti numbers of semi-algebraic sets. Aside from describing these results, we discuss briefly the background as well as the importance of these problems, and also describe the main tools from algorithmic semi-algebraic geometry, as well as algebraic topology, which make these advances possible. We end with a list of open problems.

Related

• Algorithms in Real Algebraic Geometry: A Survey
• Computing the First Betti Numberand Describing the Connected Components of Semi-algebraic Sets
• Algorithmic and topological aspects of semi-algebraic sets defined by quadratic polynomial
• Some Quantitative Results in Real Algebraic Geometry
• Computing the homology functor on semi-algebraic maps and diagrams