How to test in subexponential time whether two points can be connected by a curve in a semialgebraic set
Dima Yu. Grigoriev · 1990
A subexponential-time algorithm is designed which finds the number of connected components of a semi-algebraic set given by a quantifier-free formula of the first-order theory of real closed fields (for a rather wide class of real close fields, cf. [GV 88], [Gr 88]). Moreover, the algorithm allows for any two points from the semi-algebraic set to test, whether they belong to the same connected component.