Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-22T21:08:34.979Z Has data issue: false hasContentIssue false
  • English
  • Français

The topological configuration of a real algebraic curve

Published online by Cambridge University Press:  17 April 2009

Takis Sakkalis
Takis Sakkalis
Affiliation:
Department of Mathematical Sciences, Oakland University, Rochester MI 48309-4401, United States of America
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper presents an algorithm, motivated by Morse Theory, for the topological configuration of the components of a real algebraic curve {f(x, y) = 0}. The running time of the algorithm is O(n12 (d + log n)2 log n), where n, d are the degree and maximum coefficient size of f(x, y).

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 43 , Issue 1 , February 1991 , pp. 37 - 50
Copyright
Copyright © Australian Mathematical Society 1991

References

[l]Arnborg, S. and Feng, H., ‘Algebraic decomposition of regular curves’, J. Symbolic Comput. 5 (1988), 131–140.CrossRefGoogle Scholar
[2]Arnon, D.S., ‘Topologically reliable display of algebraic curves’, Computer Graphics 17 (1983), 219–227.CrossRefGoogle Scholar
[3]Arnon, D.S. and McCallum, S., ‘A polynomial-time algorithm for the topological type of a real algebraic curve’, J. Symbolic Comput. 5 (1988), 213–236.CrossRefGoogle Scholar
[4]Collins, G.E. and Loos, R., ‘Real zeros of polynomials’, Comput. Suppl. 4 (1982), 83–94.CrossRefGoogle Scholar
[5]Davenport, J.H., ‘Computer algebra for cylindrical algebraic decomposition’, TRITA-NA-8511, (1985), The Royal Institute of Technology.Google Scholar
[6]Gantmacher, F.R., The theory of matrices, Vols. I, II (Chelsea, 1960).Google Scholar
[7]Gianni, P. and Traverso, C., ‘Shape determination for real curves and surfaces’, Manuscript (1983).Google Scholar
[8]Milnor, J.W., Morse theory 51 (Annals of Math Studies, Princeton University Press).Google Scholar
[9]Prill, D., ‘On approximation and incidence in cylindrical algebraic decompositions’, SIAM J. Comput. 15 (1986), 972–993.CrossRefGoogle Scholar
[10]Sakkalis, T., An algorithmic application of Morse theory to real algebraic geometry, Ph.D. Dissertation (University of Rochester, 1986).Google Scholar
[11]Sakkalis, T., ‘The Euclidean algorithm and the degree of the Gauss map’, SIAM J. Comput. 19 (1990), 538–543.CrossRefGoogle Scholar
[12]Sakkalis, T., ‘On the zeros of a polynomial vector field’, IBM TR, RC 13303 (1987).Google Scholar
[13]Sakkalis, T. and Farouki, R., ‘Singular points of algebraic curves’, J. Symbolic Comput. 9 (1990), 405–421.CrossRefGoogle Scholar