On the complexity of computing with planar algebraic curves

In this paper, we give improved bounds for the computational complexity of computing with planar algebraic curves. More specifically, for arbitrary coprime polynomials ff, g∈Z[x,y]g∈Z[x,y] and an arbitrary polynomial h∈Z[x,y]h∈Z[x,y], each of total degree less than nn and with integer coefficients of absolute value less than 2τ2τ, we show that each of the following problems can be solved in a deterministic way with a number of bit operations bounded by Õ(n6+n5τ), where we ignore polylogarithmic factors in nn and ττ:
• The computation of isolating regions in  C2C2for all complex solutions   of the system f=g=0f=g=0,
• the computation of a separating form   for the solutions of f=g=0f=g=0,
• the computation of the sign of  hh at all real valued solutions of f=g=0f=g=0, and
• the computation of the topology   of the planar algebraic curve CC defined as the real valued vanishing set of the polynomial  ff. Our bound improves upon the best currently known bounds for the first three problems by a factor of n2n2 or more and closes the gap to the state-of-the-art randomized complexity for the last problem.