Computation of the topology of a real curve
Algorithmique, topologie et géométrie algébriques - Sévilla,1987, Toulouse 1988, Astérisque no. 192  (1990), p. 17-33
@incollection{AST_1990__192__17_0,
     author = {Roy, Marie-Fran\c coise},
     title = {Computation of the topology of a real curve},
     booktitle = {Algorithmique, topologie et g\'eom\'etrie alg\'ebriques - S\'evilla,1987, Toulouse 1988},
     editor = {Hayat-Legrand Claude and Sergeraert Francis},
     series = {Ast\'erisque},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {192},
     year = {1990},
     pages = {17-33},
     language = {en},
     url = {http://www.numdam.org/item/AST_1990__192__17_0}
}
Roy, Marie-Françoise. Computation of the topology of a real curve, in Algorithmique, topologie et géométrie algébriques - Sévilla,1987, Toulouse 1988, Astérisque, no. 192 (1990), pp. 17-33. http://www.numdam.org/item/AST_1990__192__17_0/

[AM] D. Arnon, S. Mc Callum : A polynomial-time algorithm for the topological type of a real algebraic curve. J. of Symbolic Computation 5 213-236 (1988).

[BKR] M. Ben-Or, D. Kozen, J. Reif: The complexity of elementary algebra and geometry. J. of Computation and Systems Sciences 32 251-264 (1986).

[BCR] J. Bochnak, M. Coste, M.-F. Roy: Géométrie algébrique réelle. Ergebnisse der Mathematik, vol. 12. Berlin Heidelberg New York: Springer Verlag (1987).

[Ca] J. Canny: Some algebraic and geometric computations in PSPACE. ACM Symposium on the theory of computation, 460-467 (1988).

[C] G. Collins: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Second GI Conference on Automata Theory and Formal Languages. Lecture Notes in Computer Sciences, vol. 33, pp. 134-183, Springer-Verlag, Berlin.

[Co] M. Coste: Effective semi-algebraic geometry. Springer Lecture Notes in Computer Science 391 1-27 (1989).

[CoR] M. Coste, M.-F. Roy: Thom's lemma, the coding of real algebraic numbers and the topology of semi-algebraic sets. J. of Symbolic Computation 5 121-130 (1988).

[CuGR] F. Cucker, L. Gonzalez, F. Rossello: On algorithms for real algebraic curves. To appear in the Proceedings of MEGA 1990.

[Cu P3R] F. Cucker, L. M. Pardo Vassallo, M. Raimondo, T. Recio, M.-F. Roy: Computation of the real analytic components of a real algebraic curve. Conférence A.A.E.C.C.-5, Minorca. Springer Lecture Notes in Computer Science 356 (1989).

[DD] C. Dicrescenzo, D. Duval: Algebraic computaion on algebraic numbers. Informatique et calcul. Wiley-Masson (1985).

[GT] P. Gianni, C. Traverso: Shape determination of real curves and surfaces. Ann. Univ. Ferrara Sez VII Sec. Math. vol XXIX 87-109 (1983).

[G] L. Gonzalez: La sucesion de Sturm-Habicht y sus aplicaciones al algebra computatcional. Thèse (University of Santander, 1989).

[GLRR 1] L. Gonzalez, H. Lombardi, T. Recio, M.-F. Roy : Spécialisation de la suite de Sturm et sous-résultants. I et II (to appear in RAIRO d'Informatique théorique).

[GLRR 2] L. Gonzalez, H. Lombardi, T. Recio, M.-F. Roy : Sturm-Habicht sequences, 136-145, ISSAC'89 Portland, ACM Press.

[Gr] D. Grigor'Ev: Complexity of deciding Tarski algebra. J. of Symbolic Computation 5 65-108 (1988).

[GrV] D. Grigor'Ev N. Vorobjov: Solving systems of polynomial inequalities in subexponential time. J. of Symbolic Computation 5 37-66 (1988).

[HRS 1] J. Heintz, M.-F. Roy, P. Solerno: Complexité du principe de Tarski-Seidenberg C.R. Acad. Sci. Paris 309 825-830 (1989).

[HRS 2] J. Heintz, M.-F. Roy, P. Solerno: Complexity of semi algebraic sets. 293-298 IFIP'89 San Francisco, North-Holand (1989).

[HRS 3] J. Heintz, M.-F. Roy, P. Solerno: Sur la complexité du principe de Tarski-Seidenberg (submitted to the Bulletin de la SMF).

[Re 1] J. Renegar : A faster PSPACE algorithm for deciding the existential theory of the reals. Technical Report 792, Cornell University Ithaca (1988).

[Re 2] J. Renegar : On the computational complexity and geometry of the first order theory of the reals. Technical Report 856, Cornell University Ithaca (1989).

[RS 1] M.-F. Roy, A. Szpirglas: Complexity of the computations on real algebraic numbers (to appear in the Journal of Symbolic Computation).

[RS 2] M.-F. Roy, A. Szpirglas: Complexity of the computation of cylindrical decomposition and topology of real algebraic curve using Thom's lemma. Géométrie Algébrique et Analytique Réelle Trento 1988. Springer Lecture Notes in Mathematics 1420 223-236 (1990).

[SS] J. T. Schwartz, M. Sharir: On the "Piano movers" problem. II. Advances in applied mathematics 4 298-351 (1983).