{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T02:29:10Z","timestamp":1750127350684,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T00:00:00Z","timestamp":1661731200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T00:00:00Z","timestamp":1661731200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Research Grants Council of the Hong Kong SAR","award":["CityU 11302418"],"award-info":[{"award-number":["CityU 11302418"]}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF 2110075"],"award-info":[{"award-number":["CCF 2110075"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100014086","name":"Fondation Sciences Math\u00e9matiques de Paris","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014086","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR JCJC GALOP (ANR-17-CE40-0009)"],"award-info":[{"award-number":["ANR JCJC GALOP (ANR-17-CE40-0009)"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007493","name":"Fondation Math\u00e9matique Jacques Hadamard","doi-asserted-by":"publisher","award":["PGMO grant ALMA"],"award-info":[{"award-number":["PGMO grant ALMA"]}],"id":[{"id":"10.13039\/501100007493","id-type":"DOI","asserted-by":"publisher"}]},{"name":"minist\u00e8re de l\u2019Europe et des Affaires \u00e9trang\u00e8res","award":["Hubert Curien Partnerships GRAPE"],"award-info":[{"award-number":["Hubert Curien Partnerships GRAPE"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00454-022-00403-x","type":"journal-article","created":{"date-parts":[[2022,8,29]],"date-time":"2022-08-29T16:03:55Z","timestamp":1661789035000},"page":"664-708","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of the Plantinga\u2013Vegter Algorithm"],"prefix":"10.1007","volume":"68","author":[{"given":"Felipe","family":"Cucker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alperen A.","family":"Erg\u00fcr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2904-1215","authenticated-orcid":false,"given":"Josu\u00e9","family":"Tonelli-Cueto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,29]]},"reference":[{"issue":"3","key":"403_CR1","doi-asserted-by":"publisher","first-page":"A1541","DOI":"10.1137\/19M1257780","volume":"42","author":"P Blanchard","year":"2020","unstructured":"Blanchard, P., Higham, N.J., Mary, T.: A class of fast and accurate summation algorithms. SIAM J. Sci. Comput. 42(3), A1541\u2013A1557 (2020)","journal-title":"SIAM J. Sci. Comput."},{"key":"403_CR2","series-title":"Grundlehren der Mathematischen Wissenschaften","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38896-5","volume-title":"Condition","author":"P B\u00fcrgisser","year":"2013","unstructured":"B\u00fcrgisser, P., Cucker, F.: Condition. Grundlehren der Mathematischen Wissenschaften, vol. 349. Springer, Heidelberg (2013)"},{"key":"403_CR3","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Cucker, F., Lairez, P.: Computing the homology of basic semialgebraic sets in weak exponential time. J. ACM 66(1), # 5 (2019)","DOI":"10.1145\/3275242"},{"issue":"4","key":"403_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.matpur.2006.06.001","volume":"86","author":"P B\u00fcrgisser","year":"2006","unstructured":"B\u00fcrgisser, P., Cucker, F., Lotz, M.: Smoothed analysis of complex conic condition numbers. J. Math. Pures Appl. 86(4), 293\u2013309 (2006)","journal-title":"J. Math. Pures Appl."},{"issue":"263","key":"403_CR5","doi-asserted-by":"publisher","first-page":"1559","DOI":"10.1090\/S0025-5718-08-02060-7","volume":"77","author":"P B\u00fcrgisser","year":"2008","unstructured":"B\u00fcrgisser, P., Cucker, F., Lotz, M.: The probability that a slightly perturbed numerical analysis problem is difficult. Math. Comput. 77(263), 1559\u20131583 (2008)","journal-title":"Math. Comput."},{"issue":"1","key":"403_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10208-019-09418-y","volume":"20","author":"P B\u00fcrgisser","year":"2020","unstructured":"B\u00fcrgisser, P., Cucker, F., Tonelli-Cueto, J.: Computing the homology of semialgebraic sets. I: Lax formulas. Found. Comput. Math. 20(1), 71\u2013118 (2020)","journal-title":"Found. Comput. Math."},{"issue":"5","key":"403_CR7","doi-asserted-by":"publisher","first-page":"1279","DOI":"10.1007\/s10208-020-09483-8","volume":"21","author":"P B\u00fcrgisser","year":"2021","unstructured":"B\u00fcrgisser, P., Cucker, F., Tonelli-Cueto, J.: Computing the homology of semialgebraic sets. II: General formulas. Found. Comput. Math. 21(5), 1279\u20131316 (2021)","journal-title":"Found. Comput. Math."},{"key":"403_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.jsc.2016.01.007","volume":"77","author":"MA Burr","year":"2016","unstructured":"Burr, M.A.: Continuous amortization and extensions: with applications to bisection-based root isolation. J. Symbol. Comput. 77, 78\u2013126 (2016)","journal-title":"J. Symbol. Comput."},{"issue":"2","key":"403_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.jsc.2011.08.021","volume":"47","author":"M Burr","year":"2012","unstructured":"Burr, M., Choi, S.W., Galehouse, B., Yap, Ch.K.: Complete subdivision algorithms. II: Isotopic meshing of singular algebraic curves. J. Symbol. Comput. 47(2), 131\u2013152 (2012)","journal-title":"J. Symbol. Comput."},{"key":"403_CR10","doi-asserted-by":"crossref","unstructured":"Burr, M.A., Gao, S., Tsigaridas, E.: The complexity of an adaptive subdivision method for approximating real curves. In: 42nd ACM International Symposium on Symbolic and Algebraic Computation (Kaiserslautern 2017), pp. 61\u201368. ACM, New York (2017)","DOI":"10.1145\/3087604.3087654"},{"key":"403_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jsc.2019.06.004","volume":"101","author":"M Burr","year":"2020","unstructured":"Burr, M., Gao, S., Tsigaridas, E.: The complexity of subdivision for diameter-distance tests. J. Symbol. Comput. 101, 1\u201327 (2020)","journal-title":"J. Symbol. Comput."},{"key":"403_CR12","unstructured":"Burr, M., Krahmer, F., Yap, Ch.: Continuous amortization: a non-probabilistic adaptive analysis technique. In: Electronic Colloquium on Computational Complexity, #\u00a0136 (2009). https:\/\/eccc.weizmann.ac.il\/report\/2009\/136\/"},{"issue":"2","key":"403_CR13","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jcom.1999.0503","volume":"15","author":"F Cucker","year":"1999","unstructured":"Cucker, F.: Approximate zeros and condition numbers. J. Complex. 15(2), 214\u2013226 (1999)","journal-title":"J. Complex."},{"key":"403_CR14","doi-asserted-by":"crossref","unstructured":"Cucker, F., Erg\u00fcr, A.A., Tonelli-Cueto, J.: Plantinga\u2013Vegter algorithm takes average polynomial time. In: 44th ACM International Symposium on Symbolic and Algebraic Computation (Beijing 2019), pp. 114\u2013121. ACM, New York (2019)","DOI":"10.1145\/3326229.3326252"},{"issue":"5\u20136","key":"403_CR15","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.jco.2008.03.001","volume":"24","author":"F Cucker","year":"2008","unstructured":"Cucker, F., Krick, T., Malajovich, G., Wschebor, M.: A numerical algorithm for zero counting. I. Complexity and accuracy. J. Complex. 24(5\u20136), 582\u2013605 (2008)","journal-title":"J. Complex."},{"issue":"2","key":"403_CR16","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s11784-009-0127-4","volume":"6","author":"F Cucker","year":"2009","unstructured":"Cucker, F., Krick, T., Malajovich, G., Wschebor, M.: A numerical algorithm for zero counting. II. Distance to ill-posedness and smoothed analysis. J. Fixed Point Theory Appl. 6(2), 285\u2013294 (2009)","journal-title":"J. Fixed Point Theory Appl."},{"issue":"1","key":"403_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.aam.2011.07.001","volume":"48","author":"F Cucker","year":"2012","unstructured":"Cucker, F., Krick, T., Malajovich, G., Wschebor, M.: A numerical algorithm for zero counting. III: Randomization and condition. Adv. Appl. Math. 48(1), 215\u2013248 (2012)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"403_CR18","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s10208-017-9358-8","volume":"18","author":"F Cucker","year":"2018","unstructured":"Cucker, F., Krick, T., Shub, M.: Computing the homology of real projective sets. Found. Comput. Math. 18(4), 929\u2013970 (2018)","journal-title":"Found. Comput. Math."},{"issue":"2","key":"403_CR19","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1137\/S1052623401386794","volume":"12","author":"F Cucker","year":"2002","unstructured":"Cucker, F., Pe\u00f1a, J.: A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine. SIAM J. Optim. 12(2), 522\u2013554 (2002)","journal-title":"SIAM J. Optim."},{"issue":"182","key":"403_CR20","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1090\/S0025-5718-1988-0929546-7","volume":"50","author":"JW Demmel","year":"1988","unstructured":"Demmel, J.W.: The probability that a numerical analysis problem is difficult. Math. Comput. 50(182), 449\u2013480 (1988)","journal-title":"Math. Comput."},{"issue":"1","key":"403_CR21","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s10208-018-9380-5","volume":"19","author":"AA Erg\u00fcr","year":"2019","unstructured":"Erg\u00fcr, A.A., Paouris, G., Rojas, J.M.: Probabilistic condition number estimates for real polynomial systems I: a broader family of distributions. Found. Comput. Math. 19(1), 131\u2013157 (2019)","journal-title":"Found. Comput. Math."},{"issue":"331","key":"403_CR22","doi-asserted-by":"publisher","first-page":"2161","DOI":"10.1090\/mcom\/3647","volume":"90","author":"AA Erg\u00fcr","year":"2021","unstructured":"Erg\u00fcr, A.A., Paouris, G., Rojas, J.M.: Smoothed analysis for the condition number of structured real polynomial systems. Math. Comput. 90(331), 2161\u20132184 (2021)","journal-title":"Math. Comput."},{"key":"403_CR23","doi-asserted-by":"crossref","unstructured":"Funke, S.: Of what use is floating-point arithmetic in computational geometry? In: Efficient Algorithms. Lecture Notes in Comput. Sci., vol. 5760, pp. 341\u2013354. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-03456-5_23"},{"key":"403_CR24","unstructured":"Galehouse, B.T.: Topologically Accurate Meshing Using Domain Subdivision Techniques. PhD thesis, New York University (2009)"},{"key":"403_CR25","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1090\/S0002-9939-1951-0041539-X","volume":"2","author":"HH Goldstine","year":"1951","unstructured":"Goldstine, H.H., von Neumann, J.: Numerical inverting of matrices of high order. II. Proc. Am. Math. Soc. 2, 188\u2013202 (1951)","journal-title":"Proc. Am. Math. Soc."},{"key":"403_CR26","volume-title":"Accuracy and Stability of Numerical Algorithms","author":"NJ Higham","year":"1996","unstructured":"Higham, N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (1996)"},{"key":"403_CR27","doi-asserted-by":"crossref","unstructured":"Jeannerod, C.-P.: Exploiting structure in floating-point arithmetic. In: Mathematical Aspects of Computer and Information Sciences (Berlin 2015). Lecture Notes in Comput. Sci., vol. 9582, pp. 25\u201334. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-32859-1_2"},{"issue":"2","key":"403_CR28","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s11856-016-1431-5","volume":"216","author":"G Livshyts","year":"2016","unstructured":"Livshyts, G., Paouris, G., Pivovarov, P.: On sharp bounds for marginal densities of product measures. Israel J. Math. 216(2), 877\u2013889 (2016)","journal-title":"Israel J. Math."},{"issue":"5","key":"403_CR29","doi-asserted-by":"publisher","first-page":"1875","DOI":"10.1090\/S0002-9939-2014-12397-5","volume":"143","author":"M Lotz","year":"2015","unstructured":"Lotz, M.: On the volume of tubular neighborhoods of real algebraic varieties. Proc. Am. Math. Soc. 143(5), 1875\u20131889 (2015)","journal-title":"Proc. Am. Math. Soc."},{"key":"403_CR30","doi-asserted-by":"crossref","unstructured":"Plantinga, S., Vegter, G.: Isotopic approximation of implicit curves and surfaces. In: 2004 Eurographics\/ACM SIGGRAPH Symposium on Geometry Processing (Nice 2004), pp. 245\u2013254. ACM, New York (2004)","DOI":"10.1145\/1057432.1057465"},{"key":"403_CR31","unstructured":"Ratschek, H., Rokne, J.: Computer Methods for the Range of Functions. Ellis Horwood Series: Mathematics and its Applications. Halsted Press, New York (1984)"},{"issue":"2","key":"403_CR32","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.aim.2008.01.010","volume":"218","author":"M Rudelson","year":"2008","unstructured":"Rudelson, M., Vershynin, R.: The Littlewood\u2013Offord problem and invertibility of random matrices. Adv. Math. 218(2), 600\u2013633 (2008)","journal-title":"Adv. Math."},{"issue":"19","key":"403_CR33","doi-asserted-by":"publisher","first-page":"9594","DOI":"10.1093\/imrn\/rnu243","volume":"2015","author":"M Rudelson","year":"2015","unstructured":"Rudelson, M., Vershynin, R.: Small ball probabilities for linear images of high-dimensional distributions. Int. Math. Res. Not. IMRN 2015(19), 9594\u20139617 (2015)","journal-title":"Int. Math. Res. Not. IMRN"},{"key":"403_CR34","doi-asserted-by":"crossref","unstructured":"Smale, S.: Complexity theory and numerical analysis. In: Acta Numer., vol.\u00a06, pp. 523\u2013551. Cambridge University Press, Cambridge (1997)","DOI":"10.1017\/S0962492900002774"},{"key":"403_CR35","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms. In: International Congress of Mathematicians (Beijing 2002), vol.\u00a01, pp. 597\u2013606. Higher Ed. Press, Beijing (2002)"},{"issue":"10","key":"403_CR36","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 77\u201384 (2009)","journal-title":"Commun. ACM"},{"key":"403_CR37","doi-asserted-by":"publisher","unstructured":"Tonelli-Cueto, J.: Condition and Homology in Semialgebraic Geometry. PhD thesis, Technische Universit\u00e4t Berlin (2019). https:\/\/doi.org\/10.14279\/depositonce-9453","DOI":"10.14279\/depositonce-9453"},{"key":"403_CR38","series-title":"Cambridge Series in Statistical and Probabilistic Mathematics","volume-title":"High-Dimensional Probability","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-Dimensional Probability. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47. Cambridge University Press, Cambridge (2018)"},{"key":"403_CR39","doi-asserted-by":"crossref","unstructured":"Xu, J., Yap, Ch.: Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis. In: 44th ACM International Symposium on Symbolic and Algebraic Computation (Beijing 2019), pp. 355\u2013362. ACM, New York (2019)","DOI":"10.1145\/3326229.3326270"},{"key":"403_CR40","doi-asserted-by":"crossref","unstructured":"Yap, Ch.: Towards soft exact computation (invited talk). In: Computer Algebra in Scientific Computing (Moscow 2019). Lecture Notes in Comput. Sci., vol. 11661, pp. 12\u201336. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-26831-2_2"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00403-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00403-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00403-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,12]],"date-time":"2022-09-12T19:04:28Z","timestamp":1663009468000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00403-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,29]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["403"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00403-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,8,29]]},"assertion":[{"value":"14 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 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":"This work was supported by the Einstein Fundation Berlin. F.C.\u00a0was partially supported by a GRF grant from the Research Grants Council of the Hong Kong SAR (project number CityU 11302418). A.E.\u00a0is supported by US National Science Foundation grant CCF 2110075. J. T.-C.\u00a0was by a postdoctoral fellowship of the 2020 \u201cInteraction\u201d program of the <i>Fondation Sciences Math\u00e9matiques de Paris<\/i>, and partially supported by ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA, and the PHC GRAPE.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}},{"value":"An extended abstract containing some of the results was presented at ISSAC\u201919\u00a0[]. Some preliminary versions of the results in Sect.\u00a0 was included in the doctoral thesis of Tonelli-Cueto\u00a0[].","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Sources"}}]}}