  We consider the problem of answering connectivity queries on a real algebraic
curve. The curve is given as the real trace of an algebraic curve, assumed to
be in generic position, and being defined by some rational parametrizations.
The query points are given by a zero-dimensional parametrization. We design an
algorithm which counts the number of connected components of the real curve
under study, and decides which query point lie in which connected component, in
time log-linear in $N^6$, where $N$ is the maximum of the degrees and
coefficient bit-sizes of the polynomials given as input. This matches the
currently best-known bound for computing the topology of real plane curves. The
main novelty of this algorithm is the avoidance of the computation of the
complete topology of the curve.
