Complexity of computing semi-algebraic descriptions of the connected components of a semi-algebraic set

Abstract

This work illustrates how to efficiently compute a semi-algebraic description of the semi-algebraically connected components of a semi-algebraic set S. In view of this, an algorithm is given that outputs a semi-algebraic description for each of the semi-algebraically connected components S. This algorithm is bounded by the complexity sk+1dO(k(3)).