  A roadmap for a semi-algebraic set $S$ is a curve which has a non-empty and
connected intersection with all connected components of $S$. Hence, this kind
of object, introduced by Canny, can be used to answer connectivity queries
(with applications, for instance, to motion planning) but has also become of
central importance in effective real algebraic geometry, since it is used in
higher-level algorithms. In this paper, we provide a probabilistic algorithm
which computes roadmaps for smooth and bounded real algebraic sets. Its output
size and running time are polynomial in $(nD)^{n\log(d)}$, where $D$ is the
maximum of the degrees of the input polynomials, $d$ is the dimension of the
set under consideration and $n$ is the number of variables. More precisely, the
running time of the algorithm is essentially subquadratic in the output size.
Even under our assumptions, it is the first roadmap algorithm with output size
and running time polynomial in $(nD)^{n\log(d)}$.
