Complexity of Computing Semi-algebraic Descriptions of the Connected Components of a Semi-algebraic Set

Given Q 2 R[X1 ; : : : ; Xk ] with deg(Q) d; we give an algorithm that outputs a semi-algebraic description for each of the semi-algebraically connected components of Z(Q) ae R k : The complexity of the algorithm as well as the size of the output are bounded by d O(k 3 ) : More generally, given any semi-algebraic set S defined by a quantifier-free formula involving a family of polynomials, P = fP1 ; : : : ; Psg ae R[X1 ; : : : ; Xk ] whose degrees are at most d; we give an algorithm that outputs a semi-algebraic description for each of the semialgebraically connected components of S: The complexity of the algorithm as well as the size of the output is bounded by s k+1 d O(k 3 ) : This improves the previously best known bound of (sd) k O(1) for this problem due to Canny, Grigor'ev, Vorobjov and Heintz, Roy and Solern`o [9, 14]. 1 Introduction Let R be a real closed field. A semi-algebraic set in R k is the set of points which satisfy a boolean combination of polynom..