We consider  the algorithmic problems of, given a real algebraic set Z,
 determining its number of connected components
and, given two points of Z to decide if they belong to the
same connected component of Z
and if so, to compute a  path with image contained in Z.
These problems are solved using the notion of roadmap.

We describe an algorithm that
computes a roadmap of Z. The complexity of the
algorithm is bounded by $(kd)^{\tilde O(k))}$ where d is the degree of the
polynomial defining Z and k is
the number of variables . Given that the
number of semi-algebraically connected components of such a variety could be
as large as $\Omega(d)^k$, this
complexity can be considered to be quasi-optimal. The best previous algorithm
for this problem had complexity $(kd)^{ O(k^1.5))}$

This is joint work with Saugata Basu.
There is related work of Mohab Safey El Din and Eric Schost on a special case.