  Let $\mathrm{R}$ be a real closed field, and $\mathrm{D} \subset \mathrm{R}$
an ordered domain. We describe an algorithm that given as input a polynomial $P
\in \mathrm{D} [ X_{1},\ldots,X_{k} ]$, and a finite set, $\mathcal{A}= \{
p_{1}, \ldots,p_{m} \}$, of points contained in $V= \mathrm{Zer}( P,
\mathrm{R}^{k})$ described by real univariate representations, computes a
roadmap of $V$ containing $\mathcal{A}$. The complexity of the algorithm,
measured by the number of arithmetic operations in $\mathrm{D} $ is bounded by
$\left( \sum_{i=1}^{m} D^{O ( \log^{2} ( k ) )}_{i} +1 \right) ( k^{\log ( k )}
d )^{O ( k\log^{2} ( k ))}$, where $d= \mathrm{deg} ( P )$, and $D_{i}$ is the
degree of the real univariate representation describing the point $p_{i}$. The
best previous algorithm for this problem had complexity $\mathrm{card} (
\mathcal{A} )^{O ( 1 )} d^{O ( k^{3/2} )}$ due to Basu, Roy, Safey-El-Din, and
Schost (2012), where it is assumed that the degrees of the polynomials
appearing in the representations of the points in $\mathcal{A}$ are bounded by
$d^{O ( k )}$. As an application of our result we prove that for any real
algebraic subset $V$ of $\mathbb{R}^{k}$ defined by a polynomial of degree $d$,
any connected component $C$ of $V$ contained in the unit ball, and any two
points of $C$, there exist a semi-algebraic path connecting them in $C$, of
length at most $( k ^{\log (k )} d )^{O ( k\log ( k ) )}$, consisting of at
most $( k ^{\log (k )} d )^{O ( k\log ( k ) )}$ curve segments of degrees
bounded by $( k ^{\log ( k )} d )^{O ( k \log ( k) )}$. While it was known
previously, by a result of D'Acunto and Kurdyka, that there always exists a
path of length $( O ( d ) )^{k-1}$ connecting two such points, there was no
upper bound on the complexity of such a path.
