{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:28:22Z","timestamp":1747189702125,"version":"3.40.5"},"reference-count":70,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:p> We give an [Formula: see text] algorithm for computing the [Formula: see text]-dimensional persistent homology of a filtration of clique complexes of cyclic graphs on [Formula: see text] vertices. This is nearly quadratic in the number of vertices [Formula: see text], and therefore a large improvement upon the traditional persistent homology algorithm, which is cubic in the number of simplices of dimension at most [Formula: see text], and hence of running time [Formula: see text] in the number of vertices\u00a0[Formula: see text]. Our algorithm applies, for example, to Vietoris\u2013Rips complexes of points sampled from a curve in [Formula: see text] when the scale is bounded depending on the geometry of the curve, but still large enough so that the Vietoris\u2013Rips complex may have non-trivial homology in arbitrarily high dimensions [Formula: see text]. In the case of the plane [Formula: see text], we prove that our algorithm applies for all scale parameters if the [Formula: see text] vertices are sampled from a convex closed differentiable curve whose convex hull contains its evolute. We ask if there are other geometric settings in which computing persistent homology is (say) quadratic or cubic in the number of vertices, instead of in the number of simplices. <\/jats:p>","DOI":"10.1142\/s0218195922500042","type":"journal-article","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T03:24:07Z","timestamp":1664508247000},"page":"1-37","source":"Crossref","is-referenced-by-count":0,"title":["The Persistent Homology of Cyclic Graphs"],"prefix":"10.1142","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0914-6316","authenticated-orcid":false,"given":"Henry","family":"Adams","sequence":"first","affiliation":[{"name":"Department of Mathematics, Colorado State University, Fort Collins, CO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sophia","family":"Coldren","sequence":"additional","affiliation":[{"name":"Colorado State University, Fort Collins, CO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9183-6062","authenticated-orcid":false,"given":"Sean","family":"Willmot","sequence":"additional","affiliation":[{"name":"Colorado State University, Fort Collins, CO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"S0218195922500042BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0166-1"},{"key":"S0218195922500042BIB002","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.2017.290.1"},{"key":"S0218195922500042BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9803-5"},{"key":"S0218195922500042BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2016.08.007"},{"key":"S0218195922500042BIB005","doi-asserted-by":"publisher","DOI":"10.1142\/S1793525319500274"},{"key":"S0218195922500042BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9916-5"},{"key":"S0218195922500042BIB007","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261258"},{"key":"S0218195922500042BIB008","doi-asserted-by":"publisher","DOI":"10.1216\/rmj.2020.50.397"},{"key":"S0218195922500042BIB009","doi-asserted-by":"publisher","DOI":"10.1112\/mtk.12010"},{"key":"S0218195922500042BIB011","first-page":"1106","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms","author":"Amenta N.","year":"2007"},{"volume-title":"Basic Topology","year":"2013","author":"Armstrong M. A.","key":"S0218195922500042BIB012"},{"key":"S0218195922500042BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9733-7"},{"key":"S0218195922500042BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.02.009"},{"key":"S0218195922500042BIB015","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511844843"},{"key":"S0218195922500042BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9034-x"},{"key":"S0218195922500042BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s41468-021-00071-5"},{"key":"S0218195922500042BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04099-8_7"},{"volume-title":"Multivariate Analysis","year":"1979","author":"Bibby J.","key":"S0218195922500042BIB019"},{"key":"S0218195922500042BIB020","doi-asserted-by":"publisher","DOI":"10.1017\/9781108297806"},{"key":"S0218195922500042BIB021","first-page":"1","volume-title":"Proceedings of the 34th Annual Symposium on Computational Geometry","author":"Boissonnat J.-D.","year":"2018"},{"key":"S0218195922500042BIB022","first-page":"55:1","volume-title":"Proceedings of the 35th Annual Symposium on Computational Geometry","author":"Boissonnat J.-D.","year":"2019"},{"key":"S0218195922500042BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-014-0247-y"},{"key":"S0218195922500042BIB024","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-09-01249-X"},{"key":"S0218195922500042BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0056-x"},{"key":"S0218195922500042BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9176-0"},{"key":"S0218195922500042BIB027","doi-asserted-by":"publisher","DOI":"10.1051\/cocv\/2009020"},{"key":"S0218195922500042BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9209-8"},{"key":"S0218195922500042BIB029","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01516.x"},{"key":"S0218195922500042BIB030","first-page":"193","author":"Chazal F.","year":"2013","journal-title":"Geometriae Dedicata"},{"key":"S0218195922500042BIB031","doi-asserted-by":"publisher","DOI":"10.1145\/1377676.1377719"},{"volume-title":"Introduction to Algorithms","year":"2009","author":"Cormen T. H.","key":"S0218195922500042BIB032"},{"key":"S0218195922500042BIB033","doi-asserted-by":"publisher","DOI":"10.1201\/9780367801700"},{"key":"S0218195922500042BIB034","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792269095"},{"key":"S0218195922500042BIB035","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582165"},{"issue":"1","key":"S0218195922500042BIB036","first-page":"1","volume":"24","author":"Dey T. K.","year":"2019","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"volume-title":"Differential Geometry of Curves and Surfaces: Revised and Updated Second Edition","year":"2016","author":"Do\u00a0Carmo M. P.","key":"S0218195922500042BIB037"},{"volume-title":"Computational Topology: An Introduction","year":"2010","author":"Edelsbrunner H.","key":"S0218195922500042BIB038"},{"key":"S0218195922500042BIB039","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892133"},{"key":"S0218195922500042BIB040","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1959-0110078-1"},{"volume-title":"H\u00f6lder and locally H\u00f6lder Continuous Functions, and Open Sets of Class ,","year":"2017","author":"Fiorenza R.","key":"S0218195922500042BIB041"},{"key":"S0218195922500042BIB042","doi-asserted-by":"publisher","DOI":"10.4310\/HHA.2019.v21.n2.a13"},{"key":"S0218195922500042BIB043","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-85-05254-8"},{"key":"S0218195922500042BIB044","doi-asserted-by":"publisher","DOI":"10.1145\/3138860.3138867"},{"key":"S0218195922500042BIB045","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89593-2_3"},{"key":"S0218195922500042BIB046","volume-title":"Spectral Theory of Random Matrices","volume":"10","author":"Girko V. L.","year":"2016"},{"key":"S0218195922500042BIB047","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"S0218195922500042BIB048","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9586-7_3"},{"volume-title":"Algebraic Topology","year":"2002","author":"Hatcher A.","key":"S0218195922500042BIB049"},{"key":"S0218195922500042BIB050","first-page":"175","volume":"138","author":"Hausmann J.-C.","year":"1995","journal-title":"Annals of Mathematics Studies"},{"key":"S0218195922500042BIB051","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9304-5"},{"key":"S0218195922500042BIB052","first-page":"852","author":"Kerber M.","year":"2017","journal-title":"Discrete & Computational Geometry"},{"key":"S0218195922500042BIB053","volume-title":"Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics","volume":"21","author":"Kozlov D. N.","year":"2008"},{"key":"S0218195922500042BIB054","doi-asserted-by":"publisher","DOI":"10.1007\/PL00000526"},{"key":"S0218195922500042BIB055","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090270"},{"key":"S0218195922500042BIB056","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.04.003"},{"key":"S0218195922500042BIB058","doi-asserted-by":"publisher","DOI":"10.1007\/s00245-002-0736-4"},{"key":"S0218195922500042BIB060","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00104-y"},{"key":"S0218195922500042BIB061","doi-asserted-by":"publisher","DOI":"10.1007\/s41468-018-0012-6"},{"key":"S0218195922500042BIB062","doi-asserted-by":"publisher","DOI":"10.1090\/noti1869"},{"key":"S0218195922500042BIB063","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2016.7472916"},{"key":"S0218195922500042BIB064","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9206-z"},{"key":"S0218195922500042BIB066","doi-asserted-by":"publisher","DOI":"10.1145\/359423.359430"},{"key":"S0218195922500042BIB068","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9513-1"},{"key":"S0218195922500042BIB069","doi-asserted-by":"publisher","DOI":"10.1007\/BF01447877"},{"key":"S0218195922500042BIB070","doi-asserted-by":"publisher","DOI":"10.3934\/dcds.2011.30.559"},{"key":"S0218195922500042BIB071","doi-asserted-by":"publisher","DOI":"10.1142\/S1793525319500444"},{"key":"S0218195922500042BIB072","doi-asserted-by":"publisher","DOI":"10.1007\/s00009-021-01699-4"},{"key":"S0218195922500042BIB073","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1941-0004644-8"},{"key":"S0218195922500042BIB074","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0038202"},{"key":"S0218195922500042BIB075","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1146-y"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195922500042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T10:15:27Z","timestamp":1666088127000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218195922500042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3]]},"references-count":70,"journal-issue":{"issue":"01n02","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.1142\/S0218195922500042"],"URL":"https:\/\/doi.org\/10.1142\/s0218195922500042","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2022,3]]}}}