A singly exponential stratification scheme for real semi-algebraic varieties and its applications (Q1177933)

The paper is, according to the authors, another step in the direction of providing singly exponential algorithms for specific real algebraic geometry problems. The main result is a stratification algorithm that gives a stratification of the real affine \(d\)-dimensional space, sign invariant with respect to a given family of \(n\) polynomials in \(d\) variables, which has \(O(n^{2d-2})\) number of cells (therefore singly exponential with respect to the number of variables), having each cell a constant description size. This number of cells is a major improvement if compared to the number of cells (doubly exponential) produced by Collin's algorithm, of a more general purpose. Moreover, it is closer to Milnor's optimal bound \(O(n^ d)\). The whole algorithm presented in this paper is also singly exponential in time, but produces polynomials which are of doubly exponential degree (in the dimension of the space). On the other hand the cell decomposition produced here has not as good topological properties as in the case of Collin's algorithm, but suffices for the applications regarded by the authors: i.e. preprocessing a set of given real algebraic varieties (each one described by a polynomial of the above mentioned family) to support a fast point location. The resulting method allows to improve current solutions for a variety of optimization problems in computational geometry.