ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Deformation techniques to deal with singular varieties. <s> We consider a family ofspolynomials, P = {P1, ?,Ps}, inkvariables with coefficients in a real closed fieldR, each of degree at mostd, and an algebraic varietyVof real dimensionk? which is defined as the zero set of a polynomialQof degree at mostd. The number of semi-algebraically connected components of all non-empty sign conditions on P overVis bounded bysk?(O(d))k. In this paper we present a new algorithm to compute a set of points meeting every semi-algebraically connected component of each non-empty sign condition of P overV. Its complexity issk? + 1dO(k). This interpolates a sequence of results between the Ben-Or?Kozen?Reif algorithm which is the casek? = 0, in one variable, and the Basu?Pollack?Roy algorithm which is the casek? =k. It improves the results where the same problem was solved in timesk? + 1dO(k?k). <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> Deformation techniques to deal with singular varieties. <s> Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets. <s> BIB002
For dealing with possibly singular algebraic sets we define when Z(Q, R k ) is a bounded algebraic set. These pseudo-critical points are a finite set of points meeting every semi-algebraically connected component of Z(Q, R k ). They are the limits of the critical points of the projection to the X 1 coordinate of a bounded nonsingular algebraic hyper-surface defined by a particular infinitesimal perturbation, Def(Q, ζ, d), of the polynomial Q (where d = deg(Q)). Moreover, the equations defining the critical points of the projection on the X 1 coordinate on the perturbed algebraic set have a very special algebraic structure (they form a Gröbner basis [17, Section 12.1]), which makes possible efficient computation of these pseudo-critical values and points. We refer the reader to BIB002 Chapter 12] for a full exposition including the definition and basic properties of Gröbner basis. The deformation Def(Q, ζ, d) of Q is defined as follows. Suppose that Z(Q, R k ) is contained in the ball of center 0 and radius 1/c. Letd be an even integer bigger than the degree d of Q and let The algebraic set Z(Def(Q, ζ, d), R ζ k ) is a bounded and non-singular hypersurface lying infinitesimally close to Z(Q, R k ) and the critical points of the projection map onto the X 1 co-ordinate restricted to Z(Def(Q, ζ, d), R ζ k ) form a finite set of points. We take the images of these points under lim ζ (cf. Definition 2.8) and we call the points obtained in this manner the X 1 -pseudo-critical points of Z(Q, R k ). Their projections on the X 1 -axis are called pseudo-critical values. Example 2.14. We illustrate the perturbation mentioned above by a concrete example. Let k = 3 and 3 ) is a bounded algebraic subset of R 3 shown below in Figure 1 . Notice that Z(Q, R 3 ) has a singularity at the origin. The surface Z(Def(Q, ζ, 4), R ζ 3 ) with a small positive real number substituted for ζ is shown in Figure 2 . Notice that this surface is non-singular, but has a different semi-algebraic homotopy type than Z(Q, R ζ 3 ) (it has three semi-algebraically connected components compared to only one of Z(Q, R ζ 3 )). However, the semi-algebraic set bounded by By computing algebraic representations (see BIB002 Section 12.4 ] for the precise definition of such a representation) of the pseudo-critical points one obtains for any given algebraic set a finite set of points guaranteed to meet every semi-algebraically connected component of this algebraic set. Using some more arguments from real algebraic geometry one can also reduce the problem of computing a finite set of points guaranteed to meet every semi-algebraically connected component of the realization of every realizable sign condition on a given family of polynomials to finding points on certain algebraic sets defined by the input polynomials (or infinitesimal perturbations of these polynomials). The details of this argument can be found in BIB002 Proposition 13.2] . The following theorem which is the best result of this kind appears in BIB001 . Theorem 2.15. Let Z(Q, R k ) be an algebraic set of real dimension k , where Q is a polynomial in R[X 1 , . . . , X k ] of degree at most d, and let P ⊂ R[X 1 , . . . , X k ] be a set of s polynomials with each P ∈ P also of degree at most d. Let D be the ring generated by the coefficients of Q and the polynomials in P. There is an algorithm which computes a set of points meeting every semi-algebraically connected component of every realizable sign condition on P over Z(Q, R ε, δ k ). The algorithm has complexity There is also an algorithm providing the list of signs of all the polynomials of P at each of these points with complexity Notice that the combinatorial complexity (i.e. the part that depends on s) of the algorithm in Theorem 2.15 depends on the dimension of the variety rather than that of the ambient space.