Topologically reliable display of algebraic curves
Author:
Open Access
- 1 July 1983
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGGRAPH Computer Graphics
- Vol. 17 (3) , 219-227
Abstract
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) .Keywords
This publication has 6 references indexed in Scilit:
- Ray tracing parametric patchesACM SIGGRAPH Computer Graphics, 1982
- Cylindrical algebraic decomposition by quantifier eliminationLecture Notes in Computer Science, 1982
- Algorithms for Graphics and Image Processing1982
- Computer AlgebraScientific American, 1981
- Automatic analysis of real algebraic curvesACM SIGSAM Bulletin, 1981
- Computer Algebra of Polynomials and Rational FunctionsThe American Mathematical Monthly, 1973