Amortized complexity bounds for polynomials with algebraic coefficients and application to curve topology

Let $P \in Z[X, Y]$ be a square-free polynomial of total degree $d$ and coefficients of bitsize $\tau$, and $C(P) := { (x,y) \in R^2, P (x,y)= 0 }$ be the real algebraic curve defined by $P$. We describe an algorithm performing no change of variable and computing the topology of $C(P)$, i.e. a straight-line planar graph isotopic to $C(P)$ inside $R^2$ in $O(d^5 \tau + d^6)$ bit operations. Our result is based on two main ingredients: First, we derive amortized quantitative bounds on the roots of polynomials with algebraic coefficients as well as adaptive methods for computing the roots of bivariate polynomial systems that actually exploit this amortization. Our second ingredient is a novel approach for the computation of the local topology of the curve in a neighborhood of all singular points.