{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:44Z","timestamp":1740109604231,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T00:00:00Z","timestamp":1708560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1910441"],"award-info":[{"award-number":["CCF-1910441"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s00454-024-00626-0","type":"journal-article","created":{"date-parts":[[2024,2,22]],"date-time":"2024-02-22T19:02:56Z","timestamp":1708628576000},"page":"622-664","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set"],"prefix":"10.1007","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2441-0915","authenticated-orcid":false,"given":"Saugata","family":"Basu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarah","family":"Percival","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,22]]},"reference":[{"issue":"1","key":"626_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009443","volume":"22","author":"S Basu","year":"1999","unstructured":"Basu, S.: On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets. Discrete Comput. Geom. 22(1), 1\u201318 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"10","key":"626_CR2","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1016\/j.jsc.2006.07.001","volume":"41","author":"S Basu","year":"2006","unstructured":"Basu, S.: Computing the first few Betti numbers of semi-algebraic sets in single exponential time. J. Symb. Comput. 41(10), 1125\u20131154 (2006)","journal-title":"J. Symb. Comput."},{"key":"626_CR3","unstructured":"Basu, S.: Algorithms in Real Algebraic Geometry: A Survey. Real Algebraic Geometry. Panorama et Synth\u00e8ses, vol.\u00a051, pp.\u00a0107\u2013153. Soci\u00e9t\u00e9 math\u00e9matique de France, Paris (2017)"},{"issue":"1","key":"626_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcom.1997.0434","volume":"13","author":"S Basu","year":"1997","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: On computing a set of points meeting every cell defined by a family of polynomials on a variety. J. Complex. 13(1), 28\u201337 (1997)","journal-title":"J. Complex."},{"issue":"1","key":"626_CR5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1090\/S0894-0347-99-00311-2","volume":"13","author":"S Basu","year":"2000","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Computing roadmaps of semi-algebraic sets on a variety. J. Am. Math. Soc. 13(1), 55\u201382 (2000)","journal-title":"J. Am. Math. Soc."},{"issue":"1","key":"626_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s00037-005-0190-1","volume":"14","author":"S Basu","year":"2005","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Computing the Euler\u2013Poincar\u00e9 characteristics of sign conditions. Comput. Complex. 14(1), 53\u201371 (2005)","journal-title":"Comput. Complex."},{"key":"626_CR7","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol.\u00a010, 2nd edn. Springer, Berlin (2006)","DOI":"10.1007\/3-540-33099-2"},{"issue":"6","key":"626_CR8","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1007\/s10208-014-9212-1","volume":"14","author":"S Basu","year":"2014","unstructured":"Basu, S., Roy, M.-F., Safey El Din, M., Schost, \u00c9.: A baby step-giant step roadmap algorithm for general algebraic sets. Found. Comput. Math. 14(6), 1117\u20131172 (2014)","journal-title":"Found. Comput. Math."},{"key":"626_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2023.36","volume":"11","author":"S Basu","year":"2023","unstructured":"Basu, S., Karisani, N.: Efficient simplicial replacement of semialgebraic sets. Forum Math. Sigma 11, e41 (2023)","journal-title":"Forum Math. Sigma"},{"key":"626_CR10","doi-asserted-by":"publisher","DOI":"10.1137\/22M1494415","author":"S Basu","year":"2023","unstructured":"Basu, S., Karisani, N.: Persistent homology of semi-algebraic sets. SIAM J. Appl. Algebra Geom. (2023). https:\/\/doi.org\/10.1137\/22M1494415","journal-title":"SIAM J. Appl. Algebra Geom."},{"issue":"1","key":"626_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10208-007-9001-1","volume":"8","author":"S Basu","year":"2008","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Computing the first Betti number of a semi-algebraic set. Found. Comput. Math. 8(1), 97\u2013136 (2008)","journal-title":"Found. Comput. Math."},{"issue":"2","key":"626_CR12","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/s00454-014-9610-9","volume":"52","author":"S Basu","year":"2014","unstructured":"Basu, S., Roy, M.-F.: Divide and conquer roadmap for algebraic sets. Discrete Comput. Geom. 52(2), 278\u2013343 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"626_CR13","doi-asserted-by":"crossref","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998) (With a foreword by Karp, R.M.)","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"626_CR14","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), Art. 5, 30 (2019) [Publication date initially given as 2018]","DOI":"10.1145\/3275242"},{"issue":"1","key":"626_CR15","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":"626_CR16","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."},{"issue":"5","key":"626_CR17","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1093\/comjnl\/36.5.504","volume":"36","author":"J Canny","year":"1993","unstructured":"Canny, J.: Computing roadmaps of general semi-algebraic sets. Comput. J. 36(5), 504\u2013514 (1993)","journal-title":"Comput. J."},{"key":"626_CR18","unstructured":"Cartan, H., Eilenberg, S.: Homological Algebra. Princeton Landmarks in Mathematics. Princeton University Press, Princeton (1999) (With an appendix by Buchsbaum, D.A., Reprint of the (1956) original)"},{"key":"626_CR19","doi-asserted-by":"crossref","unstructured":"Dey, T.K., Hou, T., Mandal, S.: Computing minimal persistent cycles: polynomial and hard cases. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a02587\u20132606. SIAM, Philadelphia (2020)","DOI":"10.1137\/1.9781611975994.158"},{"key":"626_CR20","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a01038\u20131046. ACM, New York (2005)"},{"issue":"4","key":"626_CR21","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/BF01200148","volume":"4","author":"L Gournay","year":"1993","unstructured":"Gournay, L., Risler, J.-J.: Construction of roadmaps in semi-algebraic sets. Appl. Algebra Eng. Commun. Comput. 4(4), 239\u2013252 (1993)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"issue":"2","key":"626_CR22","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01202001","volume":"2","author":"DY Grigor\u2019ev","year":"1992","unstructured":"Grigor\u2019ev, D.Y., Vorobjov, N.N., Jr.: Counting connected components of a semialgebraic set in subexponential time. Comput. Complex. 2(2), 133\u2013186 (1992)","journal-title":"Comput. Complex."},{"issue":"1\u20132","key":"626_CR23","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"DY Grigoriev","year":"1988","unstructured":"Grigoriev, D.Y., Vorobjov, N.N., Jr.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1\u20132), 37\u201364 (1988)","journal-title":"J. Symb. Comput."},{"key":"626_CR24","doi-asserted-by":"crossref","unstructured":"Heintz, J., Roy, M.-F., Solern\u00f3, P.: Single exponential path finding in semi-algebraic sets. II. The general case. In: Algebraic Geometry and Its Applications (West Lafayette, IN, 1990), pp. 449\u2013465. Springer, New York (1990)","DOI":"10.1007\/978-1-4612-2628-4_28"},{"key":"626_CR25","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"J Milnor","year":"1964","unstructured":"Milnor, J.: On the Betti numbers of real varieties. Proc. Am. Math. Soc. 15, 275\u2013280 (1964)","journal-title":"Proc. Am. Math. Soc."},{"key":"626_CR26","unstructured":"Nori, M.V.: Constructible Sheaves, Algebra, Arithmetic and Geometry, Part I, II (Mumbai, 2000). Tata Institute of Fundamental Research Studies in Mathematics, vol. 16, pp. 471\u2013491. Tata Institute of Fundamental Research Studies, Bombay (2002)"},{"issue":"4","key":"626_CR27","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1137\/17M1159439","volume":"2","author":"I Obayashi","year":"2018","unstructured":"Obayashi, I.: Volume-optimal cycle: tightest representative cycle of a generator in persistent homology. SIAM J. Appl. Algebra Geom. 2(4), 508\u2013534 (2018)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"626_CR28","first-page":"389","volume":"13","author":"IG Petrovski\u012d","year":"1949","unstructured":"Petrovski\u012d, I.G., Ole\u012dnik, O.A.: On the topology of real algebraic surfaces. Izvestiya Akad. Nauk SSSR. Ser. Mat. 13, 389\u2013402 (1949)","journal-title":"Izvestiya Akad. Nauk SSSR. Ser. Mat."},{"key":"626_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4576-6","volume-title":"An Introduction to Algebraic Topology","author":"JJ Rotman","year":"1988","unstructured":"Rotman, J.J.: An Introduction to Algebraic Topology. Springer, New York (1988)"},{"issue":"3","key":"626_CR30","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"JT Schwartz","year":"1983","unstructured":"Schwartz, J.T., Sharir, M.: On the \u201cpiano movers\u2019\u2019 problem. II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4(3), 298\u2013351 (1983)","journal-title":"Adv. Appl. Math."},{"key":"626_CR31","doi-asserted-by":"crossref","unstructured":"Thom, R.: Sur l\u2019homologie des vari\u00e9t\u00e9s alg\u00e9briques r\u00e9elles. In: Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pp. 255\u2013265. Princeton University Press, Princeton (1965)","DOI":"10.1515\/9781400874842-016"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00626-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00626-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00626-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T23:06:12Z","timestamp":1727391972000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00626-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,22]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["626"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00626-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,2,22]]},"assertion":[{"value":"30 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest. Data sharing not applicable to this article as no datasets were generated or analysed during the current study.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}