Automatic analysis of real algebraic curves

Abstract

We describe a computer program for the automatic analysis of a real plane affine algebraic curve. The input to the program is a bivariate integral polynomial F ( x, y ); the outputs are a report on the real curve defined by F ( x, y ) = 0, and a picture of the curve. The report contains the following information: whether the curve is irreducible, whether singular, and whether bounded; the number of its connected components and the dimension of each; the number of singular, turning, and level points of the curve. Approximations to these special points can be obtained to any desired precision; the more precision, the more time required. The exact form of the picture is controlled by the user; a topologically correct but "linearized" picture can be produced relatively quickly, while a more accurate drawing can be generated but requires more time. The program makes essential use of the clustering cylindrical algebraic decomposition algorithm [Arnon DS: Algorithms for the geometry of semi-algebraic sets (Dissertation). Technical Report #436, Computer Science Department, University of Wisconsin-Madison, 1981].