On the complexity of computing with planar algebraic curves

• Published in: Journal of Complexity 2015-04, Vol.31 (2), p.206-236
• Main Authors: Kobel, Alexander, Sagraloff, Michael
• Format: Article
• Language: English
• Subjects: Algebra; Approximate multipoint evaluation; Arrangement computation; Bivariate systems; Complexity; Complexity analysis; Computation; Integers; Mathematical models; Polynomials; Separating form; State of the art; Topology; Topology analysis
• ISSN: 0885-064X; 1090-2708
• DOI: 10.1016/j.jco.2014.08.002

In this paper, we give improved bounds for the computational complexity of computing with planar algebraic curves. More specifically, for arbitrary coprime polynomials f, g∈Z[x,y] and an arbitrary polynomial h∈Z[x,y], each of total degree less than n and with integer coefficients of absolute value less than 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 n and τ:•The computation of isolating regions inC2for all complex solutions of the system f=g=0,•the computation of a separating form for the solutions of f=g=0,•the computation of the sign ofh at all real valued solutions of f=g=0, and•the computation of the topology of the planar algebraic curve C defined as the real valued vanishing set of the polynomial  f. Our bound improves upon the best currently known bounds for the first three problems by a factor of n2 or more and closes the gap to the state-of-the-art randomized complexity for the last problem.