Algebraic decomposition of regular curves (Q1116997)

An algorithm is presented in the paper for computing the topological type of a nonsingular real-algebraic curve on a projective plane. The topological type is a structure including \((1)\quad the\) parity of the degree of the curve; \((2)\quad the\) number of ovals to which the curve splits; \((3)\quad 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 coefficients length.