Semi-algebraic sets appear naturally in the framework of discrete geometry, since configurations of many points in the plane
produce quite general semi-algebraic sets.
The first method we discuss, CAD (cylindrical algebraic decomposition) provided interesting results
for quantifier elimination and topology of semi-algebraic sets.
Originally used for semi-algebraic sets it became important also in the much more general framework of
o-minimal geometry. Surprizingly simple problems remain wide open even in the semi-algebraic framework.
Conceptually and algorithmically simple, and geometrically intuitive, its computational complexity is
systematically doubly exponential, while the intrinsinc complexity of the questions discussed is in most cases singly exponential.
The second method, critical point method, reaches in many cases singly exponential complexity bounds.
Equally geometrically intuitive, it is more delicate to use since it involves using infinitesimal deformations
to ensure genericity requirements. It leads to quasi optimal complexity results for quantifier elimination and relevant topological problems such as computating Euler-Poincare characteristic, deciding connectivity or computing first Betti numbers. However several topological
problems, such as computing all the Betti numbers more efficiently than with CAD, remain open. The critical point method has been also used for quadratic semi-algebraic sets, and more recently for symmetric semi-algebraic sets.
Copyright. All Rights Reserved.