On the Exact Computation of the Topology of Real Algebraic Curves (Exploiting a little more Geometry and a little less Algebra)

graph induced by one (or more) algebraic curves in the real plane.
We make no assumptions about the curves, in particular we allow
arbitrary singularities and arbitrary intersection.
This problem has been well studied for the case of a single curve.
All proposed approaches to this
problem so far require finding and counting real roots of polynomials
over an algebraic extension of Q, i.e.~the coefficients of
those polynomials are algebraic numbers. Various algebraic approaches
for this real root finding and counting problem have been developed,
but they tend to be costly unless speedups via floating point
approximations are introduced, which without additional checks
in some cases can render
the approach incorrect for some inputs.

We propose a method that is always correct and
that avoids finding and counting real roots
of polynomials with non-rational coefficients. We achieve this
using two simple geometric approaches: a triple projections method
and a curve avoidance method. We have implemented our approach for
the case of computing the topology of a single real algebraic curve.
Even this prototypical implementation without optimizations
appears to be competitive with other implementations.