{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T12:22:02Z","timestamp":1772367722686,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,10,9]],"date-time":"2010-10-09T00:00:00Z","timestamp":1286582400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s11786-010-0044-3","type":"journal-article","created":{"date-parts":[[2010,10,13]],"date-time":"2010-10-13T21:05:50Z","timestamp":1287003950000},"page":"113-137","source":"Crossref","is-referenced-by-count":35,"title":["On the Topology of Real Algebraic Plane Curves"],"prefix":"10.1007","volume":"4","author":[{"given":"Jinsan","family":"Cheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Lazard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis","family":"Pe\u00f1aranda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Pouget","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrice","family":"Rouillier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elias","family":"Tsigaridas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,10,9]]},"reference":[{"issue":"4","key":"44_CR1","doi-asserted-by":"crossref","first-page":"878","DOI":"10.1137\/0213055","volume":"13","author":"D.S. Arnon","year":"1984","unstructured":"Arnon D.S., Collins G.E., McCallum S.: Cylindrical algebraic decomposition ii: an adjacency algorithm for the plane. SIAM J. Comput. 13(4), 878\u2013889 (1984)","journal-title":"SIAM J. Comput."},{"key":"44_CR2","volume-title":"Introduction to Interval Computations","author":"G. Alefeld","year":"1983","unstructured":"Alefeld G., Herzberger J.: Introduction to Interval Computations. Academic Press, New York (1983)"},{"key":"44_CR3","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0747-7171(88)80013-0","volume":"5","author":"D. Arnon","year":"1988","unstructured":"Arnon D., McCallum S.: A polynomial time algorithm for the topological type of a real algebraic curve. J. Symb. Comput. 5, 213\u2013236 (1988)","journal-title":"J. Symb. Comput."},{"issue":"8","key":"44_CR4","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/j.cagd.2008.06.009","volume":"25","author":"L. Alberti","year":"2008","unstructured":"Alberti L., Mourrain B., Wintz J.: Topology and arrangement computation of semi-algebraic planar curves. Comput. Aided Geom. Des. 25(8), 631\u2013651 (2008)","journal-title":"Comput. Aided Geom. Des."},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Burnikel, C., Funke, S., Mehlhorn, K., Schirra, S., Schmitt, S.: A separation bound for real algebraic expressions. In: Proc. 9th Annual European Symposium on Algorithms. LNCS, vol. 2161, pp. 254\u2013265. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44676-1_21"},{"key":"44_CR6","unstructured":"Bardet, M., Faug\u00e9re, J.-C., Salvy, B.: On the complexity of Gr\u00f6bner basis computation of semi-regular overdetermined algebraic equations. In: International Conference on Polynomial System Solving, November 2004, pp. 71\u201374. Proceedings of a conference held in Paris, France in honor of Daniel Lazard"},{"key":"44_CR7","doi-asserted-by":"crossref","DOI":"10.1515\/9781400881420","volume-title":"Braids, Links, and Mapping Class Groups","author":"J. Birman","year":"1975","unstructured":"Birman J.: Braids, Links, and Mapping Class Groups. Princeton University Press, Princeton (1975)"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., Roy, M.-R.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Berlin (2006)","DOI":"10.1007\/3-540-33099-2"},{"key":"44_CR9","volume-title":"Real Algebraic and Semi-algebraic Sets, Actualites Mathematiques","author":"R. Benedetti","year":"1990","unstructured":"Benedetti R., Risler J.J.: Real Algebraic and Semi-algebraic Sets, Actualites Mathematiques. Hermann, Paris (1990)"},{"issue":"5","key":"44_CR10","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1006\/jsco.2001.0463","volume":"32","author":"C.W. Brown","year":"2001","unstructured":"Brown C.W.: Improved projection for cylindrical algebraic decomposition. J. Symb. Comput. 32(5), 447\u2013465 (2001)","journal-title":"J. Symb. Comput."},{"key":"44_CR11","unstructured":"Brown, C.W.: Contructing cylindrical algebraic decomposition of the plane quickly (2002). Manuscript http:\/\/www.usna.edu\/Users\/cs\/wcbrown\/research\/MOTS2002.1.pdf"},{"key":"44_CR12","doi-asserted-by":"crossref","unstructured":"Burr, M., Choi, S.W., Galehouse, B., Yap, C.: Complete subdivision algorithms, ii: Isotopic meshing of singular algebraic curves. In: Proc. Intl. Symp. on Symbolic & Algebraic Computation (ISSAC 2008) (2008)","DOI":"10.1145\/1390768.1390783"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"Buchberger, B.: Gr\u00f6bner bases: an algorithmic method in polynomial ideal theory. Recent trends in multidimensional systems theory. Reider ed. Bose (1985)","DOI":"10.1007\/978-94-009-5225-6_6"},{"key":"44_CR14","volume-title":"The Complexity of Robot Motion Planning","author":"J. Canny","year":"1988","unstructured":"Canny J.: The Complexity of Robot Motion Planning. MIT Press, Cambridge (1988)"},{"key":"44_CR15","unstructured":"CGAL: Computational Geometry Algorithms Library. http:\/\/www.cgal.org"},{"key":"44_CR16","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185, 2nd edn. Springer, New York (2005)"},{"key":"44_CR17","doi-asserted-by":"crossref","unstructured":"Cheng, J., Lazard, S., Pe\u00f1aranda, L., Pouget, M., Rouillier, F., Tsigaridas, E.: On the topology of planar algebraic curves. In: Proc. of the 24th European Workshop on Computational Geometry, March 2008","DOI":"10.1145\/1542362.1542424"},{"issue":"1\/2","key":"44_CR18","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0747-7171(88)80008-7","volume":"5","author":"M. Coste","year":"1988","unstructured":"Coste M., Roy M.F.: Thom\u2019s lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets. J. Symb. Comput. 5(1\/2), 121\u2013129 (1988)","journal-title":"J. Symb. Comput."},{"key":"44_CR19","first-page":"127","volume-title":"Proc. Int. Symp. Symbolic and Algebraic Computation","author":"D.I. Diochnos","year":"2007","unstructured":"Diochnos D.I., Emiris I.Z., Tsigaridas E.P.: On the complexity of real solving bivariate systems. In: Brown, C.W. (ed.) Proc. Int. Symp. Symbolic and Algebraic Computation, pp. 127\u2013134. Waterloo, Canada (2007)"},{"key":"44_CR20","unstructured":"Eigenwilling, A., Kerber, M.: Exact and efficient 2d-arrangements of arbitrary algebraic curves. In: Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA08), San Francisco, USA, January 2008, pp. 122\u2013131. ACM-SIAM, ACM\/SIAM (2008)"},{"key":"44_CR21","first-page":"138","volume-title":"CASC. LNCS, vol. 3718","author":"A. Eigenwillig","year":"2005","unstructured":"Eigenwillig A., Kettner L., Krandick W., Mehlhorn K., Schmitt S., Wolpert N.: A Descartes Algorithm for Polynomials with Bit-Stream Coefficients. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (eds) CASC. LNCS, vol. 3718, pp. 138\u2013149. Springer, Berlin (2005)"},{"key":"44_CR22","unstructured":"Eigenwillig, A., Kerber, M., Wolpert, N.: Fast and exact geometric analysis of real algebraic plane curves. In: Brown, C.W. (ed.) Proc. Int. Symp. Symbolic and Algebraic Computation, Waterwloo, Canada, 2007, pp. 151\u2013158. ACM (2007)"},{"key":"44_CR23","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/978-3-540-85521-7_4","volume-title":"Reliable Implementations of Real Number Algorithms: Theory and Practice. LNCS, vol. 5045","author":"I.Z. Emiris","year":"2008","unstructured":"Emiris I.Z., Mourrain B., Tsigaridas E.P.: Real Algebraic Numbers: Complexity Analysis and Experimentation. In: Hertling, P., Hoffmann, C., Luther, W., Revol, N. (eds) Reliable Implementations of Real Number Algorithms: Theory and Practice. LNCS, vol. 5045, pp. 57\u201382. Springer, Berlin (2008)"},{"key":"44_CR24","unstructured":"Eigenwillig, A., Sharma, V., Yap, C.K.: Almost tight recursion tree bounds for the Descartes method. In: Proc. Int. Symp. on Symbolic and Algebraic Computation, New York, NY, USA, 2006, pp. 71\u201378. ACM Press (2006)"},{"issue":"1\u20133","key":"44_CR25","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","volume":"139","author":"J.-C. Faug\u00e8re","year":"1999","unstructured":"Faug\u00e8re J.-C.: A new efficient algorithm for computing Gr\u00f6bner bases (F 4). J. Pure Appl. Algebra 139(1\u20133), 61\u201388 (1999)","journal-title":"J. Pure Appl. Algebra"},{"key":"44_CR26","unstructured":"Feng, H.: Decomposition and Computation of the Topology of Plane Real Algebraic Curves. Ph.d. thesis, The Royal Institute of Technology, Stockholm (1992)"},{"key":"44_CR27","unstructured":"FGb \u2013 A software for computing Gr\u00f6bner bases. J.-C. Faug\u00e8re. http:\/\/fgbrs.lip6.fr"},{"issue":"1","key":"44_CR28","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/jcom.2000.0571","volume":"17","author":"M. Giusti","year":"2001","unstructured":"Giusti M., Lecerf G., Salvy B.: A Gr\u00f6bner free alternative for solving polynomial systems. J. Complex. 17(1), 154\u2013211 (2001)","journal-title":"J. Complex."},{"key":"44_CR29","first-page":"227","volume-title":"Symbolic Computation and Automated Reasoning. The Calculemus-2000 Symposium","author":"G.-M. Greuel","year":"2001","unstructured":"Greuel G.-M., Pfister G., Sch\u00f6nemann H.: Singular 3.0\u2014a computer algebra system for polynomial computations. In: Kerber, M., Kohlhase, M. (eds) Symbolic Computation and Automated Reasoning. The Calculemus-2000 Symposium, pp. 227\u2013233. A. K. Peters, Ltd., Natick (2001)"},{"issue":"4","key":"44_CR30","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1006\/jcom.1996.0032","volume":"12","author":"L. Gonz\u00e1lez-Vega","year":"1996","unstructured":"Gonz\u00e1lez-Vega L., El Kahoui M.: An improved upper complexity bound for the topology computation of a real algebraic plane curve. J. Complex. 12(4), 527\u2013544 (1996)","journal-title":"J. Complex."},{"key":"44_CR31","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez-Vega, L., Lombardi, H., Recio, T., Roy, M.-F.: Sturm-Habicht Sequence. In: Proc. Int. Symp. on Symbolic and Algebraic Computation, pp. 136\u2013146 (1989)","DOI":"10.1145\/74540.74558"},{"key":"44_CR32","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez-Vega, L., Necula, I.: Efficient topology determination of implicitly defined algebraic plane curves. Comput. Aided Geom. Des. 19(9) (2002)","DOI":"10.1016\/S0167-8396(02)00167-X"},{"issue":"4\u20136","key":"44_CR33","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/S0378-4754(96)00034-1","volume":"42","author":"H. Hong","year":"1996","unstructured":"Hong H.: An efficient method for analyzing the topology of plane real algebraic curves. Math. Comput. Simul. 42(4\u20136), 571\u2013582 (1996)","journal-title":"Math. Comput. Simul."},{"key":"44_CR34","unstructured":"Kerber, M.: Analysis of real algebraic plane curves. Master\u2019s thesis, MPII (2006)"},{"key":"44_CR35","doi-asserted-by":"crossref","unstructured":"Keyser, J., Ouchi, K., Rojas, M.: The exact rational univariate representation for detecting degeneracies. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS Press, Philadelphia (2005)","DOI":"10.1090\/dimacs\/067\/12"},{"key":"44_CR36","doi-asserted-by":"crossref","unstructured":"Labs, O.: A list of challenges for real algebraic plane curve visualization software. Manuscript (2008)","DOI":"10.1007\/978-1-4419-0999-2_6"},{"key":"44_CR37","doi-asserted-by":"crossref","unstructured":"Lazard, D.: Gr\u00f6bner bases, Gaussian elimination, and resolution of systems of algebraic equations. In: EUROCAL\u201983 European Computer Algebra Conference. LNCS, vol. 162, pp. 146\u2013156. Springer, Berlin (1983)","DOI":"10.1007\/3-540-12868-9_99"},{"key":"44_CR38","doi-asserted-by":"crossref","unstructured":"Li, C., Pion, S., Yap, C.: Recent progress in exact geometric computation. J. Logic Algebraic Program. 64(1), 85\u2013111 (2004). (Special issue on \u201cPractical Development of Exact Real Number Computation\u201d)","DOI":"10.1016\/j.jlap.2004.07.006"},{"issue":"3","key":"44_CR39","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1006\/jsco.2000.0427","volume":"31","author":"T. Lickteig","year":"2001","unstructured":"Lickteig T., Roy M.-F.: Sylvester-Habicht sequences and fast Cauchy index computation. J. Symb. Comput. 31(3), 315\u2013341 (2001)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"44_CR40","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1006\/jsco.2001.0499","volume":"33","author":"S. McCallum","year":"2002","unstructured":"McCallum S., Collins G.E.: Local box adjacency algorithms for cylindrical algebraic decompositions. J. Symb. Comput. 33(3), 321\u2013342 (2002)","journal-title":"J. Symb. Comput."},{"key":"44_CR41","volume-title":"Effective Computational Geometry for Curves and Surfaces. Mathematics and Visualization, Chap. 3","author":"B. Mourrain","year":"2006","unstructured":"Mourrain B., Pion S., Schmitt S., T\u00e9court J.-P., Tsigaridas E.P., Wolpert N.: Algebraic issues in computational geometry. In: Boissonnat, J.-D., Teillaud, M. (eds) Effective Computational Geometry for Curves and Surfaces. Mathematics and Visualization, Chap. 3, Springer, Berlin (2006)"},{"key":"44_CR42","doi-asserted-by":"crossref","unstructured":"Mourrain, B., Tr\u00e9buchet, P.: Generalized normal forms and polynomial system solving. In: Proc. Int. Symp. Symbolic and Algebraic Computation, pp. 253\u2013260 (2005)","DOI":"10.1145\/1073884.1073920"},{"issue":"5","key":"44_CR43","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/s002000050114","volume":"9","author":"F. Rouillier","year":"1999","unstructured":"Rouillier F.: Solving zero-dimensional systems through the rational univariate representation. J. Appl. Algebra Eng. Commun. Comput. 9(5), 433\u2013461 (1999)","journal-title":"J. Appl. Algebra Eng. Commun. Comput."},{"key":"44_CR44","unstructured":"RS \u2013 A software for real solving of algebraic systems. F. Rouillier. http:\/\/fgbrs.lip6.fr"},{"issue":"1","key":"44_CR45","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.cam.2003.08.015","volume":"162","author":"F. Rouillier","year":"2003","unstructured":"Rouillier F., Zimmermann P.: Efficient isolation of polynomial real roots. J. Comput. Appl. Math. 162(1), 33\u201350 (2003)","journal-title":"J. Comput. Appl. Math."},{"key":"44_CR46","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1017\/S0004972700028756","volume":"43","author":"T. Sakkalis","year":"1991","unstructured":"Sakkalis T.: The topological configuration of a real algebraic curve. Bull. Aust. Math. Soc. 43, 37\u201350 (1991)","journal-title":"Bull. Aust. Math. Soc."},{"issue":"4","key":"44_CR47","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/S0747-7171(08)80019-3","volume":"9","author":"T. Sakkalis","year":"1990","unstructured":"Sakkalis T., Farouki R.: Singular points of algebraic curves. J. Symb. Comput. 9(4), 405\u2013421 (1990)","journal-title":"J. Symb. Comput."},{"issue":"9","key":"44_CR48","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1016\/j.jsc.2006.06.004","volume":"41","author":"A. Strzebonski","year":"2006","unstructured":"Strzebonski A.: Cylindrical algebraic decomposition using validated numerics. J. Symb. Comput. 41(9), 1021\u20131038 (2006)","journal-title":"J. Symb. Comput."},{"key":"44_CR49","doi-asserted-by":"crossref","unstructured":"Seidel, R., Wolpert, N.: On the exact computation of the topology of real algebraic curves. In: Proc 21st ACM Symposium on Computational Geometry, pp. 107\u2013115 (2005)","DOI":"10.1145\/1064092.1064111"},{"key":"44_CR50","unstructured":"Teissier, B.: Cycles \u00e9vanescents, sections planes et conditions de Whitney. (french). In: Singularit\u00e9s \u00e0 Carg\u00e8se (Rencontre Singularit\u00e9s G\u00e9om. Anal., Inst. \u00c9tudes Sci., Carg\u00e8se, 1972). Asterisque, vol. 7\u20138, pp. 285\u2013362. Soc. Math. France, Paris (1973)"},{"key":"44_CR51","volume-title":"Modern Computer Algebra","author":"J. Gathen von zur","year":"2003","unstructured":"von zur Gathen J., Gerhard J.: Modern Computer Algebra, 2nd edn. Cambridge University Press, Cambridge (2003)","edition":"2"},{"key":"44_CR52","volume-title":"Fundamental Problems of Algorithmic Algebra","author":"C.K. Yap","year":"2000","unstructured":"Yap C.K.: Fundamental Problems of Algorithmic Algebra. Oxford University Press, Oxford (2000)"},{"key":"44_CR53","unstructured":"Yap, C.K.: Complete subdivision algorithms, I: intersection of B\u00e9zier curves. In: Amenta, N., Cheong, O. (eds.) Proceedings of the 22nd ACM Symposium on Computational Geometry, Sedona, Arizona, USA, June 5\u20137, 2006, pp. 217\u2013226. ACM (2006)"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0044-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-010-0044-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-010-0044-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T08:52:46Z","timestamp":1559724766000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-010-0044-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,9]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["44"],"URL":"https:\/\/doi.org\/10.1007\/s11786-010-0044-3","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,9]]}}}