A polynomial-time algorithm for the topological type of real algebraic curve (Q1115496)

An algorithm is presented for computing the topological type of a nonsingular real-algebraic curve on a projective plane. The topological type is a structure including (1) the parity of the degree of the curve; (2) the number of ovals into which the curve splits; (3) partial ordering of ovals by inclusion. The algorithm works for curves defined by integral homogeneous polynomials. It is based on cylindrical algebraic decomposition and has polynomial complexity assessed as a nice \(O(n^{27}L(d)^ 3)\) where n is the degree of the defining polynomial and L(d) is the total length of the coefficients.