TY - JOUR

T1 - A polynomial-time algorithm for the topological type of a real algebraic curve

AU - Arnon, Dennis S.

AU - McCallum, Scott

PY - 1988/1/1

Y1 - 1988/1/1

N2 - It was proved over a century ago that an algebraic curve C in the real projective plane, of degree n, has at most (n−1)(n−2)/2+1 connected components. If C is nonslngular, then each of its commponents is a topological circle. A circle in the projectlve plane either separates it into a disk (the interior of the circle) and a Möbius band (the circle's exterior), or does not separate it. In the former case, the circle is an oval. If C is nonsingular, then all its components are ovals if n is even, and all except one are ovals if n is odd. An oval is included in another if it lies in the other's interior. The topological type of (a nonsingular) C is completely determined by (1) the parity of n, (2) how many ovals it has, and (3) the partial ordering of its ovals by inclusion. We present an algorithm which, given a homogeneous polinomial f(x,y,z) of degree n with integer coefficients, checks whether tlte curve defined hy f = 0 is nonsingular and if so, computes its topological type. The algorithm's maximum computing time is O(n27L(d)3), where d is the sum of the absolute values of the integer coofficients of f, and L(d) is the length of d.

AB - It was proved over a century ago that an algebraic curve C in the real projective plane, of degree n, has at most (n−1)(n−2)/2+1 connected components. If C is nonslngular, then each of its commponents is a topological circle. A circle in the projectlve plane either separates it into a disk (the interior of the circle) and a Möbius band (the circle's exterior), or does not separate it. In the former case, the circle is an oval. If C is nonsingular, then all its components are ovals if n is even, and all except one are ovals if n is odd. An oval is included in another if it lies in the other's interior. The topological type of (a nonsingular) C is completely determined by (1) the parity of n, (2) how many ovals it has, and (3) the partial ordering of its ovals by inclusion. We present an algorithm which, given a homogeneous polinomial f(x,y,z) of degree n with integer coefficients, checks whether tlte curve defined hy f = 0 is nonsingular and if so, computes its topological type. The algorithm's maximum computing time is O(n27L(d)3), where d is the sum of the absolute values of the integer coofficients of f, and L(d) is the length of d.

UR - http://www.scopus.com/inward/record.url?scp=84971721358&partnerID=8YFLogxK

U2 - 10.1016/S0747-7171(88)80013-0

DO - 10.1016/S0747-7171(88)80013-0

M3 - Article

AN - SCOPUS:84971721358

VL - 5

SP - 213

EP - 236

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

SN - 0747-7171

IS - 1-2

ER -