{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T06:15:02Z","timestamp":1777616102021,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00454-021-00353-w","type":"journal-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T17:03:16Z","timestamp":1644944596000},"page":"631-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Bounds for Polynomials on Algebraic Numbers and Application to Curve Topology"],"prefix":"10.1007","volume":"67","author":[{"given":"Daouda Niang","family":"Diatta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e9ny","family":"Diatta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrice","family":"Rouillier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6955-6491","authenticated-orcid":false,"given":"Marie-Fran\u00e7oise","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Sagraloff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"key":"353_CR1","doi-asserted-by":"crossref","unstructured":"Alberti, L., Mourrain, B.: Regularity criteria for the topology of algebraic curves and surfaces. In: Mathematics of Surfaces XII (Sheffield 2007). Lecture Notes in Computer Science, vol. 4647, pp. 1\u201328. Springer, Berlin\u2013Heidelberg (2007)","DOI":"10.1007\/978-3-540-73843-5_1"},{"key":"353_CR2","doi-asserted-by":"crossref","unstructured":"Alberti, L., Mourrain, B.: Visualisation of implicit algebraic curves. In: 15th Pacific Conference on Computer Graphics and Applications (Maui 2007), pp. 303\u2013312. IEEE, Los Alamitos (2007)","DOI":"10.1109\/PG.2007.32"},{"issue":"8","key":"353_CR3","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., Wintz, J.: Topology and arrangement computation of semi-algebraic planar curves. Comput. Aided Geom. Design 25(8), 631\u2013651 (2008)","journal-title":"Comput. Aided Geom. Design"},{"key":"353_CR4","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10. Springer, Berlin (2006). Revised version at http:\/\/perso.univ-rennes1.fr\/marie-francoise.roy\/","DOI":"10.1007\/3-540-33099-2"},{"key":"353_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.jsc.2017.03.009","volume":"86","author":"R Becker","year":"2018","unstructured":"Becker, R., Sagraloff, M., Sharma, V., Yap, C.: A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration. J. Symb. Comput. 86, 51\u201396 (2018)","journal-title":"J. Symb. Comput."},{"key":"353_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2013.04.014","volume":"491","author":"E Berberich","year":"2013","unstructured":"Berberich, E., Emeliyanenko, P., Kobel, A., Sagraloff, M.: Exact symbolic-numeric computation of planar algebraic curves. Theoret. Comput. Sci. 491, 1\u201332 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"353_CR7","doi-asserted-by":"crossref","unstructured":"Bodrato, M., Zanoni, A.: Long integers and polynomial evaluation with Estrin\u2019s scheme. In: 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (Timi\u015foara 2011), pp. 39\u201346. IEEE, Los Alamitos (2011)","DOI":"10.1109\/SYNASC.2011.17"},{"key":"353_CR8","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., Pouget, M., Rouillier, F., Sagraloff, M.: Solving bivariate systems using rational univariate representations. J. Complexity 37, 34\u201375 (2016)","journal-title":"J. Complexity"},{"key":"353_CR9","doi-asserted-by":"crossref","unstructured":"Burr, M., Choi, S.W., Galehouse, B., Yap, Ch.K.: Complete subdivision algorithms.\u00a0II. Isotopic meshing of singular algebraic curves. In: 21st International Symposium on Symbolic and Algebraic Computation (Linz\/Hagenberg 2008), pp. 87\u201394. ACM, New York (2008)","DOI":"10.1145\/1390768.1390783"},{"issue":"1","key":"353_CR10","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s11786-010-0044-3","volume":"4","author":"J Cheng","year":"2010","unstructured":"Cheng, J., Lazard, S., Pe\u00f1aranda, L., Pouget, M., Rouillier, F., Tsigaridas, E.: On the topology of real algebraic plane curves. Math. Comput. Sci. 4(1), 113\u2013137 (2010)","journal-title":"Math. Comput. Sci."},{"key":"353_CR11","doi-asserted-by":"crossref","unstructured":"Diatta, D.N., Mourrain, B., Ruatta, O.: On the computation of the topology of a non-reduced implicit space curve. In: 21st International Symposium on Symbolic and Algebraic Computation (Linz\/Hagenberg 2008), pp. 47\u201354. ACM, New York (2008)","DOI":"10.1145\/1390768.1390778"},{"key":"353_CR12","doi-asserted-by":"crossref","unstructured":"Eigenwillig, A., Kerber, M., Wolpert, N.: Fast and exact geometric analysis of real algebraic plane curves. In: 20th International Symposium on Symbolic and Algebraic Computation (Waterloo 2007), pp. 151\u2013158. ACM, New York (2007)","DOI":"10.1145\/1277548.1277570"},{"key":"353_CR13","volume-title":"Modern Computer Algebra","author":"J von zur Gathen","year":"1999","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, New York (1999)"},{"issue":"4","key":"353_CR14","doi-asserted-by":"publisher","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. Complexity 12(4), 527\u2013544 (1996)","journal-title":"J. Complexity"},{"issue":"9","key":"353_CR15","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0167-8396(02)00167-X","volume":"19","author":"L Gonzalez-Vega","year":"2002","unstructured":"Gonzalez-Vega, L., Necula, I.: Efficient topology determination of implicitly defined algebraic plane curves. Comput. Aided Geom. Design 19(9), 719\u2013743 (2002)","journal-title":"Comput. Aided Geom. Design"},{"key":"353_CR16","unstructured":"Kerber, M.: Geometric Algorithms for Algebraic Curves and Surfaces. PhD thesis, Universit\u00e4t des Saarlandes (2009). https:\/\/d-nb.info\/1002267331\/34"},{"issue":"3","key":"353_CR17","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., Sagraloff, M.: A worst-case bound for topology computation of algebraic curves. J. Symb. Comput. 47(3), 239\u2013258 (2012)","journal-title":"J. Symb. Comput."},{"key":"353_CR18","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.cam.2014.11.031","volume":"280","author":"M Kerber","year":"2015","unstructured":"Kerber, M., Sagraloff, M.: Root refinement for real polynomials using quadratic interval refinement. J. Comput. Appl. Math. 280, 377\u2013395 (2015)","journal-title":"J. Comput. Appl. Math."},{"issue":"2","key":"353_CR19","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., Sagraloff, M.: On the complexity of computing with planar algebraic curves. J. Complexity 31(2), 206\u2013236 (2015)","journal-title":"J. Complexity"},{"key":"353_CR20","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Sagraloff, M., Wang, P.: From approximate factorization to root isolation. In: 38th International Symposium on Symbolic and Algebraic Computation (Boston 2013), pp. 283\u2013290. ACM, New York (2013)","DOI":"10.1145\/2465506.2465523"},{"key":"353_CR21","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jsc.2014.02.001","volume":"66","author":"K Mehlhorn","year":"2015","unstructured":"Mehlhorn, K., Sagraloff, M., Wang, P.: From approximate factorization to root isolation with application to cylindrical algebraic decomposition. J. Symb. Comput. 66, 34\u201369 (2015)","journal-title":"J. Symb. Comput."},{"issue":"5","key":"353_CR22","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1006\/jsco.2002.0531","volume":"33","author":"VY Pan","year":"2002","unstructured":"Pan, V.Y.: Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. J. Symb. Comput. 33(5), 701\u2013733 (2002)","journal-title":"J. Symb. Comput."},{"key":"353_CR23","doi-asserted-by":"crossref","unstructured":"Pan, V.Y., Tsigaridas, E.P.: On the Boolean complexity of real root refinement. In: 38th International Symposium on Symbolic and Algebraic Computation (Boston 2013), pp. 299\u2013306. ACM, New York (2013)","DOI":"10.1145\/2465506.2465938"},{"key":"353_CR24","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.jsc.2015.03.004","volume":"73","author":"M Sagraloff","year":"2016","unstructured":"Sagraloff, M., Mehlhorn, K.: Computing real roots of real polynomials. J. Symb. Comput. 73, 46\u201386 (2016)","journal-title":"J. Symb. Comput."},{"key":"353_CR25","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.jsc.2017.12.001","volume":"92","author":"A Strzebonski","year":"2019","unstructured":"Strzebonski, A., Tsigaridas, E.: Univariate real root isolation in an extension field and applications. J.\u00a0Symb. Comput. 92, 31\u201351 (2019)","journal-title":"J.\u00a0Symb. Comput."},{"key":"353_CR26","doi-asserted-by":"crossref","unstructured":"Wintz, J., Mourrain, B.: A subdivision arrangement algorithm for semi-algebraic curves: an overview. In: 15th Pacific Conference on Computer Graphics and Applications (Maui 2007), pp. 449\u2013452. IEEE, Los Alamitos (2007)","DOI":"10.1109\/PG.2007.18"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00353-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-021-00353-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-021-00353-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T17:08:21Z","timestamp":1726679301000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-021-00353-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,15]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["353"],"URL":"https:\/\/doi.org\/10.1007\/s00454-021-00353-w","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,15]]},"assertion":[{"value":"27 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Data sharing"}}]}}