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

Dennis S. Arnon*, Scott McCallum

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

49 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)213-236
Number of pages24
JournalJournal of Symbolic Computation
Volume5
Issue number1-2
DOIs
Publication statusPublished - 1 Jan 1988
Externally publishedYes

Fingerprint Dive into the research topics of 'A polynomial-time algorithm for the topological type of a real algebraic curve'. Together they form a unique fingerprint.

Cite this