{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T00:56:53Z","timestamp":1746320213281},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T00:00:00Z","timestamp":1610409600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T00:00:00Z","timestamp":1610409600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Syst Sci Complex"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s11424-020-9164-2","type":"journal-article","created":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T03:31:44Z","timestamp":1610508704000},"page":"809-826","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of Computing the Topology of Real Algebraic Space Curves"],"prefix":"10.1007","volume":"34","author":[{"given":"Kai","family":"Jin","sequence":"first","affiliation":[]},{"given":"Jinsan","family":"Cheng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,12]]},"reference":[{"key":"9164_CR1","doi-asserted-by":"crossref","unstructured":"Cheng J S, Gao X S, and Li M, Determining the topology of real algebraic surfaces, Mathematics of Surfaces, Springer-Verlag, 2005, 121\u2013146.","DOI":"10.1007\/11537908_8"},{"key":"9164_CR2","doi-asserted-by":"publisher","first-page":"903","DOI":"10.1016\/j.jsc.2011.09.010","volume":"47","author":"D N Diatta","year":"2012","unstructured":"Diatta D N, Mourrain B, and Ruatta O, On the isotopic meshing of an algebraic implicit surface, Journal Symbolic Computation, 2012, 47: 903\u2013925.","journal-title":"Journal Symbolic Computation"},{"issue":"4\u20136","key":"9164_CR3","doi-asserted-by":"publisher","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, Mathematics and Computers in Simulation, 1996, 42(4\u20136): 571\u2013582.","journal-title":"Mathematics and Computers in Simulation"},{"key":"9164_CR4","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0747-7171(88)80013-0","volume":"5","author":"D S Arnon","year":"1998","unstructured":"Arnon D S and McCallum S, A polynomial-time algorithm for the topological type of a real algebraic curve, Journal of Symbolic Computation, 1998, 5: 213\u2013236.","journal-title":"Journal of Symbolic Computation"},{"issue":"2","key":"9164_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jsco.2002.0544","volume":"34","author":"D Bouziane","year":"2002","unstructured":"Bouziane D and El Kahoui D, Computation of the dual of a plane projective curve, Journal of Symbolic Computation, 2002, 34(2): 105\u2013117.","journal-title":"Journal of Symbolic Computation"},{"issue":"2","key":"9164_CR6","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s11424-012-1145-7","volume":"25","author":"B Gao","year":"2012","unstructured":"Gao B and Chen Y F, Finding the topology of implicitly defined two algebraic plane curves, Journal of Systems Science & Complexity, 2012, 25(2): 362\u2013374.","journal-title":"Journal of Systems Science & Complexity"},{"issue":"1","key":"9164_CR7","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/s11424-020-8262-5","volume":"33","author":"K Jin","year":"2020","unstructured":"Jin K and Cheng J S, On the topology and isotopic meshing of plane algebraic curves, Journal of Systems Science & Complexity, 2020, 33(1): 230\u2013260.","journal-title":"Journal of Systems Science & Complexity"},{"key":"9164_CR8","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0167-8396(02)00167-X","volume":"19","author":"L Gonz\u00e1lez-Vega","year":"2002","unstructured":"Gonz\u00e1lez-Vega L and Necula I, Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, 2002, 19: 719\u2013743.","journal-title":"Computer Aided Geometric Design"},{"key":"9164_CR9","doi-asserted-by":"crossref","unstructured":"Eigenwillig A, Kerber M, and Wolpert N, Fast and exact geometric analysis of real algebraic plane curves, Proc. ISSAC 2007, ACM Press, 2007, 151\u2013158.","DOI":"10.1145\/1277548.1277570"},{"issue":"8","key":"9164_CR10","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/j.cagd.2008.06.009","volume":"25","author":"L Alberti","year":"2008","unstructured":"Alberti L, Mourrain B, and Wintz J, Topology and arrangement computation of semi-algebraic planar curves, Computer Aided Geometry Design, 2008, 25(8): 631\u2013651.","journal-title":"Computer Aided Geometry Design"},{"key":"9164_CR11","doi-asserted-by":"crossref","unstructured":"Burr M, Choi S, Galehouse B, et al, Complete subdivision algorithms, ii: Isotopic meshing of algebraic curves, Proc. ACM ISSAC 2008, ACM Press, 2008, 87\u201394.","DOI":"10.1145\/1390768.1390783"},{"key":"9164_CR12","unstructured":"Eigenwillig A and Kerber M, Exact and efficient 2d-arrangements of arbitrary algebraic curves, Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA08), San Francisco, USA, ACM-SIAM, ACM\/SIAM, 2008, 122\u2013131."},{"key":"9164_CR13","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s11786-010-0044-3","volume":"4","author":"J S Cheng","year":"2010","unstructured":"Cheng J S, Lazard S, Pe\u00f1aranda L, et al., On the topology of the real algebraic plane curves, Mathematics in Computer Science, 2010, 4: 113\u2013117.","journal-title":"Mathematics in Computer Science"},{"key":"9164_CR14","doi-asserted-by":"crossref","unstructured":"Berberich E, Emeliyanenko P, Kobel A, et al., Arrangement computation for planar algebraic curves, Proc. 4th Internal Workshop on Symbolic-Numeric Computation, ACM, San Jose, USA, 2011, 88\u201399.","DOI":"10.1145\/2331684.2331698"},{"key":"9164_CR15","first-page":"99","volume":"11077","author":"C B Chen","year":"2018","unstructured":"Chen C B and Wu W Y, A continuation method for visualizing planar real algebraic curves with singularities, Computer Algebra in Scientific Computing, Lecture Notes in Comput. Sci., Springer, Cham, 2018, 11077: 99\u2013115.","journal-title":"Computer Algebra in Scientific Computing, Lecture Notes in Comput. Sci., Springer, Cham"},{"key":"9164_CR16","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.jco.2014.08.002","volume":"31","author":"A Kobel","year":"2015","unstructured":"Kobel A and Sagraloff M, On the complexity of computing with planar algebraic curves, Journal of Complexity, 2015, 31: 206\u2013236.","journal-title":"Journal of Complexity"},{"key":"9164_CR17","doi-asserted-by":"crossref","unstructured":"Seidel R and Wolpert N, On the exact computation of the topology of real algebraic curves, Proc. of the 21st Annual ACM Symposium on Computational Geometry, 2005, 107\u2013115.","DOI":"10.1145\/1064092.1064111"},{"key":"9164_CR18","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/j.jsc.2005.01.006","volume":"39","author":"J G Alc\u00e1zar","year":"2005","unstructured":"Alc\u00e1zar J G and Sendra J R, Computation of the topology of real algebraic space curves, Journal of Symbolic Computation, 2005, 39: 719\u2013744.","journal-title":"Journal of Symbolic Computation"},{"key":"9164_CR19","first-page":"74","volume":"8660","author":"J S Cheng","year":"2014","unstructured":"Cheng J S and Jin K, Finding a deterministic generic position for an algebraic space curve, CASC 2014, Springer, LNCS, 2014, 8660: 74\u201384.","journal-title":"CASC 2014, Springer, LNCS"},{"key":"9164_CR20","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jsc.2013.06.004","volume":"58","author":"J S Cheng","year":"2013","unstructured":"Cheng J S, Jin K, and Lazard D, Certified rational parametric approximation of real algebraic space curves with local generic position method, Journal of Symbolic Computation, 2013, 58: 18\u201340.","journal-title":"Journal of Symbolic Computation"},{"key":"9164_CR21","unstructured":"Diatta D N, Mourrain B, and Ruatta O, On the computation of the topology of a non-reduced implicit space curve, ISSAC 2008, 2008, 47\u201354."},{"key":"9164_CR22","doi-asserted-by":"crossref","unstructured":"Gatellier G, Labrouzy A, Mourrain B, et al., Computing the topology of 3-dimensional algebraic curves, Computational Methods for Algebraic Spline Surfaces, Springer-Verlag, 2005, 27\u201344.","DOI":"10.1007\/3-540-27157-0_3"},{"key":"9164_CR23","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/j.jsc.2007.10.008","volume":"43","author":"M El Kahoui","year":"2008","unstructured":"El Kahoui M, Topology of real algebraic space curves, Journal of Symbolic Computation, 2008, 43: 235\u2013258.","journal-title":"Journal of Symbolic Computation"},{"key":"9164_CR24","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1145\/2631948.2631970","volume-title":"Proceedings of the 2014 Symposium on Symbolic-Numeric Computation (SNC\u201914)","author":"K Jin","year":"2014","unstructured":"Jin K and Cheng J S, Isotopic epsilon-meshing of real algebraic space curves, Proceedings of the 2014 Symposium on Symbolic-Numeric Computation (SNC\u201914), ACM, New York, NY, USA, 2014, 118\u2013127."},{"key":"9164_CR25","doi-asserted-by":"crossref","unstructured":"Cheng J S, Gao X S, and Li J, Root isolation for bivariate polynomial systems with local generic position method, ISSAC 2009, 2009, 103\u2013110.","DOI":"10.1145\/1576702.1576719"},{"issue":"276","key":"9164_CR26","doi-asserted-by":"publisher","first-page":"2143","DOI":"10.1090\/S0025-5718-2011-02462-2","volume":"80","author":"B Dayton","year":"2011","unstructured":"Dayton B, Li T Y, and Zeng Z G, Multiple zeros of nonlinear systems, Mathematics of Computation, 2011, 80(276): 2143\u20132168.","journal-title":"Mathematics of Computation"},{"key":"9164_CR27","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1006\/jcom.1996.0032","volume":"12","author":"L Gonz\u00e1lez-Vaga","year":"1996","unstructured":"Gonz\u00e1lez-Vaga L and El Kahoui M, An improved upper complexity bound for the topology computation of a real algebraic plane curve, Journal of Complexity, 1996, 12: 527\u2013544.","journal-title":"Journal of Complexity"},{"key":"9164_CR28","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.jsc.2011.11.001","volume":"47","author":"M Kerber","year":"2012","unstructured":"Kerber M and Sagraloff M, A worst-case bound for the topology computation of algebraic curves, Journal of Symbolic Computation, 2012, 47: 239\u2013258.","journal-title":"Journal of Symbolic Computation"},{"key":"9164_CR29","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.jsc.2014.09.017","volume":"68","author":"J S Cheng","year":"2015","unstructured":"Cheng J S and Jin K, A generic position based method for real root isolation of zero-dimensional polynomial systems, Journal of Symbolic Computation, 2015, 68: 204\u2013224.","journal-title":"Journal of Symbolic Computation"},{"key":"9164_CR30","doi-asserted-by":"crossref","unstructured":"Bouzidi Y, Lazard S, Pouget M, et al., Rational univariate representations of bivariate systems and applications, ISSAC 2013, ACM, 2013, 109\u2013116.","DOI":"10.1145\/2465506.2465519"},{"key":"9164_CR31","doi-asserted-by":"crossref","unstructured":"Emeliyanenko P and Sagraloff M, On the complexity of solving a bivariate polynomial system, Proc. ISSAC 2012, ACM, 2012, 154\u2013161.","DOI":"10.1145\/2442829.2442854"},{"key":"9164_CR32","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jco.2016.07.002","volume":"37","author":"Y Bouzidi","year":"2016","unstructured":"Bouzidi Y, Lazard S, Moroz G, et al., Solving bivariate systems using rational univariate representations, Journal of Complexity, 2016, 37: 34\u201375.","journal-title":"Journal of Complexity"},{"key":"9164_CR33","doi-asserted-by":"crossref","unstructured":"Basu S, Pollack R, and Roy M, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, 2nd Edition, Springer, 2006.","DOI":"10.1007\/3-540-33099-2"},{"issue":"7","key":"9164_CR34","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.jsc.2008.04.009","volume":"44","author":"D I Diochnos","year":"2009","unstructured":"Diochnos D I, Emiris I Z, and Tsigaridas E P, On the asymptotic and practical complexity of solving bivariate systems over the reals, Journal Symbolic Computation, 2009, 44(7): 818\u2013835.","journal-title":"Journal Symbolic Computation"},{"key":"9164_CR35","doi-asserted-by":"crossref","unstructured":"Pan V Y and Tsigaridas E P, On the boolen complexity of real root refinement, Proc. ISSAC 2013, ACM, 2013, 299\u2013306.","DOI":"10.1145\/2465506.2465938"},{"key":"9164_CR36","doi-asserted-by":"crossref","unstructured":"Sagraloff M, When Newton meets descartes: A simple and fast algorithm to isolate the real roots of a polynomial, Proc. ISSAC 2012, ACM, 2012, 297\u2013304.","DOI":"10.1145\/2442829.2442872"},{"key":"9164_CR37","doi-asserted-by":"crossref","unstructured":"Mignotte M, Mathematics for Computer Algebra, Springer-Verlag, 1992.","DOI":"10.1007\/978-1-4613-9171-5"},{"key":"9164_CR38","volume-title":"Fundamental Problems in Algorithmic Algebra","author":"C Yap","year":"2000","unstructured":"Yap C, Fundamental Problems in Algorithmic Algebra, Oxford University Press, UK, 2000."}],"container-title":["Journal of Systems Science and Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11424-020-9164-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11424-020-9164-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11424-020-9164-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T22:34:42Z","timestamp":1613687682000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11424-020-9164-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,12]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["9164"],"URL":"https:\/\/doi.org\/10.1007\/s11424-020-9164-2","relation":{},"ISSN":["1009-6124","1559-7067"],"issn-type":[{"value":"1009-6124","type":"print"},{"value":"1559-7067","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,12]]},"assertion":[{"value":"13 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}