{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:05:19Z","timestamp":1750309519921,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T00:00:00Z","timestamp":1722470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["W1230 and P 33765-N"],"award-info":[{"award-number":["W1230 and P 33765-N"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,8,31]]},"abstract":"<jats:p>\n            For a finite set of balls of radius\n            <jats:italic>r<\/jats:italic>\n            , the\n            <jats:italic>k<\/jats:italic>\n            -fold cover is the space covered by at least\n            <jats:italic>k<\/jats:italic>\n            balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the\n            <jats:italic>k<\/jats:italic>\n            -fold filtration of the centers. For\n            <jats:italic>k<\/jats:italic>\n            =1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger\n            <jats:italic>k<\/jats:italic>\n            , it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the\n            <jats:italic>k<\/jats:italic>\n            -fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case\n            <jats:italic>k<\/jats:italic>\n            =1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points. Our method also extends to the multicover bifiltration, composed of the\n            <jats:italic>k<\/jats:italic>\n            -fold filtrations for several values of\n            <jats:italic>k<\/jats:italic>\n            , with the same size and complexity bounds.\n          <\/jats:p>","DOI":"10.1145\/3666085","type":"journal-article","created":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T11:56:31Z","timestamp":1716810991000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparse Higher Order \u010cech Filtrations"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1372-1531","authenticated-orcid":false,"given":"Micka\u00ebl","family":"Buchet","sequence":"first","affiliation":[{"name":"Geometry Institute, Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4827-4663","authenticated-orcid":false,"given":"Bianca","family":"B Dornelas","sequence":"additional","affiliation":[{"name":"Geometry Institute, Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8030-9299","authenticated-orcid":false,"given":"Michael","family":"Kerber","sequence":"additional","affiliation":[{"name":"Geometry Institute, Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2019.58"},{"key":"e_1_3_2_3_2","unstructured":"Ulrich Bauer Michael Kerber Fabian Roll and Alexander Rolle. 2022. A Unified View on the Functorial Nerve Theorem and its Variations. arxiv:2203.03571"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29726-8_17"},{"key":"e_1_3_2_5_2","unstructured":"Andrew J. Blumberg and Michael Lesnick. 2020. Stability of 2-Parameter Persistent Homology. arXiv:2010.09628"},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","unstructured":"Andrew J. Blumberg and Michael Lesnick. 2022. Universality of the Homotopy Interleaving Distance. arxiv:1705.01690 [math.AT]","DOI":"10.1090\/tran\/8738"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-39441-1_3"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-014-0247-y"},{"key":"e_1_3_2_9_2","unstructured":"Bernhard Brehm and Hanne Hardering. 2018. Sparips. arXiv:1807.09982"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2016.07.001"},{"key":"e_1_3_2_11_2","volume-title":"39th Symposium on Computational Geometry (SoCG 2023)","author":"Buchet Micka\u00ebl","year":"2023","unstructured":"Micka\u00ebl Buchet, Bianca Dornelas, and Michael Kerber. 2023. Sparse higher order \u010cech filtrations. In 39th Symposium on Computational Geometry (SoCG 2023)."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-09-01249-X"},{"key":"e_1_3_2_13_2","volume-title":"Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, August 10-12","author":"Cavanna Nicholas J.","year":"2015","unstructured":"Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy. 2015. A geometric perspective on sparse filtrations. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, August 10-12. Queen\u2019s University, Ontario, Canada, Kingston, Ontario, Canada. DOI:http:\/\/research.cs.queensu.ca\/cccg2015\/CCCG15-papers\/01.pdf"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542362.1542407"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9098-0"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.166"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9951-2"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41468-021-00072-4"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-022-00476-8"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582165"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3284360"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142681"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/069"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2885-2"},{"key":"e_1_3_2_27_2","unstructured":"Herbert Edelsbrunner and Georg Osang. 2020. A Simple Algorithm for Higher-order Delaunay Mosaics and Alpha Shapes. arxiv:2011.03617"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-021-00281-9"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187681"},{"key":"e_1_3_2_30_2","volume-title":"Smallest Enclosing Balls of Balls: Combinatorial Structure & Algorithms","author":"Fischer Kaspar","year":"2005","unstructured":"Kaspar Fischer. 2005. Smallest Enclosing Balls of Balls: Combinatorial Structure & Algorithms. Ph. D. Dissertation. Swiss Federal Institute of Technology, ETH Z\u00fcrich. DOI:https:\/\/people.inf.ethz.ch\/emo\/DoctThesisFiles\/fischer05.pdf"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195904001500"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13160-014-0153-5"},{"key":"e_1_3_2_33_2","volume-title":"Elementary Applied Topology","author":"Ghrist Robert W.","year":"2014","unstructured":"Robert W. Ghrist. 2014. Elementary Applied Topology. Vol. 1. Createspace Seattle, WA."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-012-9465-x"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/173"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_3_2_38_2","volume-title":"Algebraic Topology","author":"Hatcher Allen","year":"2005","unstructured":"Allen Hatcher. 2005. Algebraic Topology. Cambridge University Press."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1520877113"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12021-017-9341-1"},{"key":"e_1_3_2_41_2","volume-title":"Categories for the Working Mathematician.","author":"Lane Saunders Mac","year":"1998","unstructured":"Saunders Mac Lane. 1998. Categories for the Working Mathematician. Vol. 5. New York, NY: Springer. xii + 314 pages."},{"key":"e_1_3_2_42_2","volume-title":"GUDHI User and Reference Manual (3.5.0 ed.)","author":"Maria Cl\u00e9ment","year":"2022","unstructured":"Cl\u00e9ment Maria, Pawel Dlotko, Vincent Rouvreau, and Marc Glisse. 2022. Rips complex. In GUDHI User and Reference Manual (3.5.0 ed.). GUDHI Editorial Board. DOI:https:\/\/gudhi.inria.fr\/doc\/3.5.0\/group_rips_complex.html"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187750"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1811002"},{"key":"e_1_3_2_45_2","volume-title":"Topology (2nd ed.)","author":"Munkres James","year":"2000","unstructured":"James Munkres. 2000. Topology (2nd ed.). Prentice Hall."},{"key":"e_1_3_2_46_2","unstructured":"Julian B. P\u00e9rez Sydney Hauke Umberto Lupo Matteo Caorsi and Alberto Dassatti. 2021. Giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris-Rips Filtrations. arXiv:2107.05412"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SOCG.2015.857"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/41958.41977"},{"key":"e_1_3_2_49_2","first-page":"309","volume-title":"Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012, August 8-10","author":"Sheehy Donald R.","year":"2012","unstructured":"Donald R. Sheehy. 2012. A multicover nerve for geometric inference. In Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012, August 8-10. Charlottetown, Prince Edward Island, Canada, 309\u2013314. DOI:http:\/\/2012.cccg.ca\/papers\/paper52.pdf"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9513-1"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2021.58"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780199563074.001.0001"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3666085","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3666085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:05Z","timestamp":1750295885000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3666085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8,31]]}},"alternative-id":["10.1145\/3666085"],"URL":"https:\/\/doi.org\/10.1145\/3666085","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2024,8]]},"assertion":[{"value":"2023-05-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-05-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}