ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.2. <s> A sweep auger radially mounted within a storage bin is rotatable horizontally across the bin floor about a vertical axis located centrally of the bin. An upright distributing auger arranged coaxially with the vertical axis has its lower end adjacent the inner end of the sweep auger and its upper end spaced from the roof of the bin. The sweep auger is of a construction such that for each complete revolution across the bin floor it moves predetermined volumes of material over given axial sections thereof for delivery to the distributing auger. The material or grain discharged from the distributing auger is spread across the top surface of the grain stored in the bin. All of the grain in the bin is thus acted upon continuously for circulation through the bin for drying purposes. Field grain may be introduced through the roof of the bin for concurrent distribution and circulation with the grain already in the bin. A bin unloading auger is located below the bin floor to receive grain directly from the sweep auger for discharge exteriorly of the bin. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.2. <s> This paper is devoted to the following result: letR be a real closed field and letS be a semialgebraic subset ofRn defined by a boolean combination of polynomial inequalities. LetD be the sum of the degrees of the polynomials involved. Then it is possible to find algorithmically a description of the semialgebraically connected components ofS in sequential timeDno(1) and parallel time (n logD)o(1) This implies that the problem of finding the connected components of a semialgebraic set can be solved in P-SPACE. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.2. <s> In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data. A new feature of this algorithm is that the role of the algebraic part (the dependence on the degrees of the imput polynomials) and the combinatorial part (the dependence on the number of polynomials) are sparated. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that is output, are independent of the number of input polynomials. As special cases of this algorithm new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields, are obtained. <s> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.2. <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> BIB004 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.2. <s> Let a semialgebraic set be defined by a quantifier-free formula with atomic subformulas of the form fi>0, 0,1 ≦ i ≦ where the polynomials fieℤ[X1,..., Xn] of degree deg (fi)<d have absolute value of the coefficients at most 2M. An algorithm is constructed which finds the connected components of the semialgebraic set (i.e., giving formulas for them) in a time that is polynomial inM (kd)ro(1). Collins' previously known method has a bound which is polynomial inM (kd)ro(1). <s> BIB005
The critical points method and singly exponential algorithms. As mentioned earlier, all algorithms using cylindrical algebraic decomposition have doubly exponential complexity. Algorithms with singly exponential complexity for solving problems in semi-algebraic geometry are mostly based on the critical points method. This method was pioneered by several researchers including Grigoriev and Vorobjov BIB001 BIB005 , Renegar  , Canny  , Heintz, Roy and Solernò BIB002 , Basu, Pollack and Roy BIB003 amongst others. In simple terms, the critical points method is nothing but a method for finding at least one point in every semialgebraically connected component of an algebraic set. It can be shown that for a bounded nonsingular algebraic hyper-surface, it is possible to change coordinates so that its projection to the X 1 -axis has a finite number of non-degenerate critical points. These points provide at least one point in every semi-algebraically connected component of the bounded nonsingular algebraic hyper-surface. Unfortunately this is not very useful in algorithms since it provides no method for performing this linear change of variables. Moreover when we deal with the case of a general algebraic set, which may be unbounded or singular, this method no longer works. In order to reduce the general case to the case of bounded nonsingular algebraic sets, we use an important technique in algorithmic semi-algebraic geometrynamely, perturbation of a given real algebraic set in R k using one or more infinitesimals. The perturbed variety is then defined over a non-archimedean real closed extension of the ground field -namely the field of algebraic Puiseux series in the infinitesimal elements with coefficients in R. Since the theory behind such extensions might be unfamiliar to some readers, we introduce here the necessary algebraic background referring the reader to [  It is a straightforward exercise to verify that the field of all Puiseux series in ε with coefficients in R is an ordered field. The order extends the order of R, and ε is an infinitesimally small and positive, i.e. is positive and smaller than any positive r ∈ R. Notation 1. The field of Puiseux series in ε with coefficients in R contains as a subfield, the field of Puiseux series which are algebraic over R [ε] . We denote by R ε the field of algebraic Puiseux series in ε with coefficients in R. We will also use the notation R ε 1 , . . . , ε m to denote the field R ε 1 · · · ε m . Notice that in the field R ε 1 , . . . , ε m we have the ordering 0 < ε m ε m−1 · · · ε 1 1 where the symbol a b means that a is infinitesimally small with respect to b. The following theorem is classical (see for example [17, Section 2.6] for a proof). Theorem 2.7. The field R ε is real closed. Definition 2.8 (The lim ε map). When a ∈ R ε is bounded by an element of R, lim ε (a) is the constant term of a, obtained by substituting 0 for ε in a. Since we will often consider the semi-algebraic sets defined by the same formula, but over different real closed extensions of the ground field, the following notation is useful. Notation 2. Let R be a real closed field containing R. Given a semi-algebraic set S in R k , the extension of S to R , denoted Ext(S, R ), is the semi-algebraic subset of R k defined by the same quantifier free formula that defines S. The set Ext(S, R ) is well defined (i.e. it only depends on the set S and not on the quantifier free formula chosen to describe it). This is an easy consequence of the transfer principle. We now return to the discussion of the critical points method. In order for the critical points method to work for all algebraic sets, we associate to a possibly unbounded algebraic set Z ⊂ R k a bounded algebraic set Z b ⊂ R ε k+1 , whose semi-algebraically connected components are closely related to those of Z. Let Z = Z(Q, R k ) and consider The variety Z b is the intersection of the sphere S k (0, 1/ε) of center 0 and radius 1 ε with a cylinder based Ext(Z, R ε ) (and is hence bounded over R ε ). The intersection of Z b with the hyper-plane X k+1 = 0 is the intersection of Z with the sphere S k−1 (0, 1/ε) of center 0 and radius 1 ε . Denote by π the projection from R ε k+1 to R ε k . The following proposition which appears in BIB004 then relates the semi-algebraically connected component of Z with those of Z b and this allows us to reduce the problem of finding points on every semi-algebraically connected component of a possibly unbounded algebraic set to the same problem on bounded algebraic sets. Proposition 2.10. Let N be a finite number of points meeting every semi-algebraically connected component of Z b . Then π(N ) meets every semi-algebraically connected component of the extension Ext(Z, R ε ). We obtain immediately using Proposition 2.10 a method for finding a point in every semi-algebraically connected component of an algebraic set. Note that these points have coordinates in the extension R ε rather than in the real closed field R we started with. However, the extension from R to R ε preserves semi-algebraically connected components.