“Topologically reliable display of algebraic curves” by Arnon

An algebraic curve is a set of points in the plane satisfying an equation F(x,y) = 0, where F(x,y) is a polynomial in x and y with rational number coefficients. The topological structure of an algebraic curve can be complicated. It may, for example, have multiple components, isolated points, or intricate self-crossings. In the field of Computer Algebra (Symbolic Mathematical Computation), algorithms for exact computations on polynomials with rational number coefficients have been developed. In particular, the cylindrical algebraic decomposition (cad) algorithm of Computer Algebra determines the topological structure of an algebraic curve, given F(x,y) as input. We describe methods for algebraic curve display which, by making use of the cad algorithm, correctly portray the topological structure of the curve. The running times of our algorithms consist almost entirely of the time required for the cad algorithm, which varies from seconds to hours depending on the particular F(x,y).

1. DS Arnon, “Automatic analysis of real algebraic curves,” SIGSAM Bulletin (of the Association for Computing Machinery)15, pp. 3-9 (1981).
2. DS Arnon, “Algorithms for the geometry of semialgebraic sets,” Technical Report #436, Computer Science Dept., University of Wisconsin, Madison,Wisconsin(1981). (Ph.D. thesis)
3. DS Arnon, GE Collins, and S McCallum, “Cylindrical algebraic decomposition II: an adjacency algorithm for the plane,” Technical Report CSD TR-428, Computer Science Dept., Purdue University(December, 1982).
4. DS Arnon and S McCallum, “Cylindrical algebraic decomposition by quantifier elimination,” pp. 215-222 in Proceedings of the European Computer Algebra Conference (EUROCAM ’82), ed. J Calmet,Lecture Notes in Computer Science, 144, Springer-Verlag, Berlin(1982).
5. DS Arnon, GE Collins, and S McCallum, “Cylindrical algebraic decomposition I: the basic algorithm,” Technical Report CSD TR-427, Computer Science Dept., Purdue University(December, 1982).
6. GE Collins, “Computer algebra of polynomials and rational functions,” American Mathematical Monthly80, pp. 725-755 (1973).
7. GE Collins, “Quantifier elimination for real closed fields by cylindrical algebraic decomposition,” pp. 134-163 in Proceedings of the Second GI Conference on Automata and Formal Languages, Lecture notes in Computer Science, 33, Springer-Verlag, Berlin(1975).
8. GE Collins, “SAC-2 and ALDES now available,” SIGSAM Bulletin (of the Association for Computing Machinery)14, p. 19 (1980).
9. JT Kajiya, “Ray tracing parametric patches,” Computer Graphics16, pp. 245-254 (1982).
10. R Pavelle, M Rothstein, and J Fitch, “Computer algebra,” Scientific American245, pp. 136-152 (1981).
11. T Pavlidis, Algorithms for graphics and image processing, Computer Science Press, Rockville, Maryland(1982).
12. DR Stoutemyer and DYY Yun, “Symbolic mathematical computation,” in Encyclopedia of Computer Science and Technology, ed. J Belzer, AG Holzman, A Kent,Marcel Dekker(1980). (Supplement)