[{"acknowledgement":"Both authors are partially supported by the European Research Council (ERC) Horizon 2020 project\r\n‘Alpha Shape Theory Extended’, grant no. 788183. The first author is also partially supported by the DFG\r\nCollaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund\r\n(FWF), grant no. I 02979-N35.","arxiv":1,"article_processing_charge":"No","date_published":"2024-08-29T00:00:00Z","title":"Merge trees of periodic filtrations","date_updated":"2026-04-07T12:54:09Z","external_id":{"arxiv":["2408.16575"]},"month":"08","oa_version":"Preprint","abstract":[{"text":"Motivated by applications to crystalline materials, we generalize the merge tree and the related barcode of a filtered complex to the periodic setting in Euclidean space. They are invariant under isometries, changing bases, and indeed changing lattices. In addition, we prove stability under perturbations and provide an algorithm that under mild geometric conditions typically satisfied by crystalline materials takes O((n+m)logn) time, in which n and m are the numbers of vertices and edges in the quotient complex, respectively.\r\n","lang":"eng"}],"citation":{"ama":"Edelsbrunner H, Heiss T. Merge trees of periodic filtrations. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2408.16575\">10.48550/arXiv.2408.16575</a>","ieee":"H. Edelsbrunner and T. Heiss, “Merge trees of periodic filtrations,” <i>arXiv</i>. .","mla":"Edelsbrunner, Herbert, and Teresa Heiss. “Merge Trees of Periodic Filtrations.” <i>ArXiv</i>, doi:<a href=\"https://doi.org/10.48550/arXiv.2408.16575\">10.48550/arXiv.2408.16575</a>.","short":"H. Edelsbrunner, T. Heiss, ArXiv (n.d.).","ista":"Edelsbrunner H, Heiss T. Merge trees of periodic filtrations. arXiv, <a href=\"https://doi.org/10.48550/arXiv.2408.16575\">10.48550/arXiv.2408.16575</a>.","apa":"Edelsbrunner, H., &#38; Heiss, T. (n.d.). Merge trees of periodic filtrations. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2408.16575\">https://doi.org/10.48550/arXiv.2408.16575</a>","chicago":"Edelsbrunner, Herbert, and Teresa Heiss. “Merge Trees of Periodic Filtrations.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2408.16575\">https://doi.org/10.48550/arXiv.2408.16575</a>."},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2408.16575"}],"related_material":{"record":[{"id":"18667","relation":"dissertation_contains","status":"public"}]},"status":"public","type":"preprint","year":"2024","date_created":"2024-12-18T14:06:57Z","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"last_name":"Heiss","first_name":"Teresa","orcid":"0000-0002-1780-2689","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","full_name":"Heiss, Teresa"}],"language":[{"iso":"eng"}],"project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes","call_identifier":"FWF"}],"doi":"10.48550/arXiv.2408.16575","publication_status":"draft","oa":1,"department":[{"_id":"HeEd"}],"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"18673","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"29","publication":"arXiv","corr_author":"1","OA_place":"repository"},{"department":[{"_id":"HeEd"}],"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"18981","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"09","publication":"arXiv","corr_author":"1","OA_place":"repository","year":"2024","date_created":"2025-01-31T17:03:04Z","author":[{"full_name":"Brown, Adam","last_name":"Brown","first_name":"Adam"},{"full_name":"Draganov, Ondrej","id":"2B23F01E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-0464-3823","last_name":"Draganov","first_name":"Ondrej"}],"language":[{"iso":"eng"}],"project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"name":"Mathematics, Computer Science","call_identifier":"FWF","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes","call_identifier":"FWF"}],"doi":"10.48550/arXiv.2209.14993","publication_status":"draft","oa":1,"oa_version":"Preprint","citation":{"mla":"Brown, Adam, and Ondrej Draganov. “Discrete Microlocal Morse Theory.” <i>ArXiv</i>, doi:<a href=\"https://doi.org/10.48550/arXiv.2209.14993\">10.48550/arXiv.2209.14993</a>.","short":"A. Brown, O. Draganov, ArXiv (n.d.).","ista":"Brown A, Draganov O. Discrete microlocal Morse theory. arXiv, <a href=\"https://doi.org/10.48550/arXiv.2209.14993\">10.48550/arXiv.2209.14993</a>.","apa":"Brown, A., &#38; Draganov, O. (n.d.). Discrete microlocal Morse theory. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2209.14993\">https://doi.org/10.48550/arXiv.2209.14993</a>","chicago":"Brown, Adam, and Ondrej Draganov. “Discrete Microlocal Morse Theory.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2209.14993\">https://doi.org/10.48550/arXiv.2209.14993</a>.","ama":"Brown A, Draganov O. Discrete microlocal Morse theory. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2209.14993\">10.48550/arXiv.2209.14993</a>","ieee":"A. Brown and O. Draganov, “Discrete microlocal Morse theory,” <i>arXiv</i>. ."},"abstract":[{"lang":"eng","text":"We establish several results combining discrete Morse theory and microlocal sheaf theory in the setting of finite posets and simplicial complexes. Our primary tool is a computationally tractable description of the bounded derived category of sheaves on a poset with the Alexandrov topology. We prove that each bounded complex of sheaves on a finite poset admits a unique (up to isomorphism of complexes) minimal injective resolution, and we provide algorithms for computing minimal injective resolution of an injective complex, as well as several useful functors between derived categories of sheaves. For the constant sheaf on a simplicial complex, we give asymptotically tight bounds on the complexity of computing the minimal injective resolution using those algorithms. Our main result is a novel definition of the discrete microsupport of a bounded complex of sheaves on a finite poset. We detail several foundational properties of the discrete microsupport, as well as a microlocal generalization of the discrete homological Morse theorem and Morse inequalities."}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2209.14993","open_access":"1"}],"related_material":{"record":[{"id":"20323","relation":"later_version","status":"public"},{"relation":"dissertation_contains","id":"18979","status":"public"}]},"status":"public","type":"preprint","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize,\r\nAustrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR\r\n109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35.","article_processing_charge":"No","date_published":"2024-06-09T00:00:00Z","arxiv":1,"title":"Discrete microlocal Morse theory","date_updated":"2026-04-07T11:47:29Z","external_id":{"arxiv":["2209.14993"]},"month":"06"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"18998","conference":{"name":"EMNLP: Conference on Empirical Methods in Natural Language Processing","end_date":"2024-11-16","start_date":"2024-11-12","location":"Miami, FL, United States"},"department":[{"_id":"GradSch"},{"_id":"HeEd"}],"page":"12080-12099","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","day":"01","OA_place":"publisher","corr_author":"1","publication":"Findings of the Association for Computational Linguistics: EMNLP 2024","year":"2024","date_created":"2025-02-04T16:19:28Z","file_date_updated":"2025-02-10T08:20:34Z","ddc":["500"],"language":[{"iso":"eng"}],"author":[{"orcid":"0000-0003-0464-3823","first_name":"Ondrej","last_name":"Draganov","full_name":"Draganov, Ondrej","id":"2B23F01E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Skiena, Steven","first_name":"Steven","last_name":"Skiena"}],"publication_status":"published","oa":1,"file":[{"creator":"dernst","checksum":"f4416a5962194f0181ab0dc7f9ef93c0","access_level":"open_access","file_name":"2024_EMNLP_Draganov.pdf","date_created":"2025-02-10T08:20:34Z","file_id":"19016","success":1,"file_size":1312638,"date_updated":"2025-02-10T08:20:34Z","content_type":"application/pdf","relation":"main_file"}],"doi":"10.18653/v1/2024.findings-emnlp.705","citation":{"ieee":"O. Draganov and S. Skiena, “The shape of word embeddings: Quantifying non-isometry with topological data analysis,” in <i>Findings of the Association for Computational Linguistics: EMNLP 2024</i>, Miami, FL, United States, 2024, pp. 12080–12099.","ama":"Draganov O, Skiena S. The shape of word embeddings: Quantifying non-isometry with topological data analysis. In: <i>Findings of the Association for Computational Linguistics: EMNLP 2024</i>. Association for Computational Linguistics; 2024:12080-12099. doi:<a href=\"https://doi.org/10.18653/v1/2024.findings-emnlp.705\">10.18653/v1/2024.findings-emnlp.705</a>","apa":"Draganov, O., &#38; Skiena, S. (2024). The shape of word embeddings: Quantifying non-isometry with topological data analysis. In <i>Findings of the Association for Computational Linguistics: EMNLP 2024</i> (pp. 12080–12099). Miami, FL, United States: Association for Computational Linguistics. <a href=\"https://doi.org/10.18653/v1/2024.findings-emnlp.705\">https://doi.org/10.18653/v1/2024.findings-emnlp.705</a>","chicago":"Draganov, Ondrej, and Steven Skiena. “The Shape of Word Embeddings: Quantifying Non-Isometry with Topological Data Analysis.” In <i>Findings of the Association for Computational Linguistics: EMNLP 2024</i>, 12080–99. Association for Computational Linguistics, 2024. <a href=\"https://doi.org/10.18653/v1/2024.findings-emnlp.705\">https://doi.org/10.18653/v1/2024.findings-emnlp.705</a>.","mla":"Draganov, Ondrej, and Steven Skiena. “The Shape of Word Embeddings: Quantifying Non-Isometry with Topological Data Analysis.” <i>Findings of the Association for Computational Linguistics: EMNLP 2024</i>, Association for Computational Linguistics, 2024, pp. 12080–99, doi:<a href=\"https://doi.org/10.18653/v1/2024.findings-emnlp.705\">10.18653/v1/2024.findings-emnlp.705</a>.","ista":"Draganov O, Skiena S. 2024. The shape of word embeddings: Quantifying non-isometry with topological data analysis. Findings of the Association for Computational Linguistics: EMNLP 2024. EMNLP: Conference on Empirical Methods in Natural Language Processing, 12080–12099.","short":"O. Draganov, S. Skiena, in:, Findings of the Association for Computational Linguistics: EMNLP 2024, Association for Computational Linguistics, 2024, pp. 12080–12099."},"scopus_import":"1","abstract":[{"lang":"eng","text":"Word embeddings represent language vocabularies as clouds of d-dimensional points. We investigate how information is conveyed by the general shape of these clouds, instead of representing the semantic meaning of each token. Specifically, we use the notion of persistent homology from topological data analysis (TDA) to measure the distances between language pairs from the shape of their unlabeled embeddings. These distances quantify the degree of non-isometry of the embeddings. To distinguish whether these differences are random training errors or capture real information about the languages, we use the computed distance matrices to construct language phylogenetic trees over 81 Indo-European languages. Careful evaluation shows that our reconstructed trees exhibit strong and statistically-significant similarities to the reference."}],"oa_version":"Published Version","publisher":"Association for Computational Linguistics","OA_type":"gold","type":"conference","status":"public","title":"The shape of word embeddings: Quantifying non-isometry with topological data analysis","arxiv":1,"article_processing_charge":"No","date_published":"2024-11-01T00:00:00Z","external_id":{"arxiv":["2404.00500"]},"quality_controlled":"1","date_updated":"2025-02-10T08:21:37Z","month":"11"},{"OA_type":"green","type":"preprint","status":"public","abstract":[{"lang":"eng","text":"Exploring the shape of point configurations has been a key driver in the evolution of TDA (short for topological data analysis) since its infancy. This survey illustrates the recent efforts to broaden these ideas to model spatial interactions among multiple configurations, each distinguished by a color. It describes advances in this area and prepares the ground for further exploration by mentioning unresolved questions and promising research avenues while focusing on the overlap with discrete geometry."}],"citation":{"ieee":"S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “Chromatic topological data analysis,” <i>arXiv</i>. .","ama":"Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. Chromatic topological data analysis. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/ARXIV.2406.04102\">10.48550/ARXIV.2406.04102</a>","apa":"Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., &#38; Saghafian, M. (n.d.). Chromatic topological data analysis. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/ARXIV.2406.04102\">https://doi.org/10.48550/ARXIV.2406.04102</a>","chicago":"Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “Chromatic Topological Data Analysis.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/ARXIV.2406.04102\">https://doi.org/10.48550/ARXIV.2406.04102</a>.","mla":"Cultrera di Montesano, Sebastiano, et al. “Chromatic Topological Data Analysis.” <i>ArXiv</i>, 2406.04102, doi:<a href=\"https://doi.org/10.48550/ARXIV.2406.04102\">10.48550/ARXIV.2406.04102</a>.","short":"S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, ArXiv (n.d.).","ista":"Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. Chromatic topological data analysis. arXiv, 2406.04102."},"article_number":"2406.04102","oa_version":"Preprint","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2406.04102","open_access":"1"}],"external_id":{"arxiv":["2406.04102"]},"date_updated":"2025-02-10T08:14:27Z","month":"06","title":"Chromatic topological data analysis","article_processing_charge":"No","date_published":"2024-06-06T00:00:00Z","arxiv":1,"day":"06","corr_author":"1","OA_place":"repository","publication":"arXiv","_id":"18999","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"GradSch"},{"_id":"HeEd"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","ddc":["510"],"language":[{"iso":"eng"}],"author":[{"full_name":"Cultrera di Montesano, Sebastiano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6249-0832","last_name":"Cultrera di Montesano","first_name":"Sebastiano"},{"orcid":"0000-0003-0464-3823","first_name":"Ondrej","last_name":"Draganov","full_name":"Draganov, Ondrej","id":"2B23F01E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824","last_name":"Saghafian","first_name":"Morteza"}],"oa":1,"publication_status":"submitted","doi":"10.48550/ARXIV.2406.04102","year":"2024","date_created":"2025-02-04T16:21:21Z"},{"title":"Understanding higher-order interactions in information space","date_published":"2024-08-01T00:00:00Z","article_processing_charge":"Yes","acknowledgement":"We thank Anton Nikitenko for first observing that the Wrap complex can be characterized as stated in Claim (ii) of the Wrap Complex Lemma, and Ondrej Draganov for correcting a critical mistake in one of our formulas in Section 2.","isi":1,"volume":26,"month":"08","external_id":{"isi":["001305543500001"],"pmid":["39202107"]},"quality_controlled":"1","date_updated":"2025-09-08T09:13:44Z","publisher":"MDPI","article_number":"637","scopus_import":"1","citation":{"chicago":"Edelsbrunner, Herbert, Katharina Ölsböck, and Hubert Wagner. “Understanding Higher-Order Interactions in Information Space.” <i>Entropy</i>. MDPI, 2024. <a href=\"https://doi.org/10.3390/e26080637\">https://doi.org/10.3390/e26080637</a>.","apa":"Edelsbrunner, H., Ölsböck, K., &#38; Wagner, H. (2024). Understanding higher-order interactions in information space. <i>Entropy</i>. MDPI. <a href=\"https://doi.org/10.3390/e26080637\">https://doi.org/10.3390/e26080637</a>","ista":"Edelsbrunner H, Ölsböck K, Wagner H. 2024. Understanding higher-order interactions in information space. Entropy. 26(8), 637.","short":"H. Edelsbrunner, K. Ölsböck, H. Wagner, Entropy 26 (2024).","mla":"Edelsbrunner, Herbert, et al. “Understanding Higher-Order Interactions in Information Space.” <i>Entropy</i>, vol. 26, no. 8, 637, MDPI, 2024, doi:<a href=\"https://doi.org/10.3390/e26080637\">10.3390/e26080637</a>.","ieee":"H. Edelsbrunner, K. Ölsböck, and H. Wagner, “Understanding higher-order interactions in information space,” <i>Entropy</i>, vol. 26, no. 8. MDPI, 2024.","ama":"Edelsbrunner H, Ölsböck K, Wagner H. Understanding higher-order interactions in information space. <i>Entropy</i>. 2024;26(8). doi:<a href=\"https://doi.org/10.3390/e26080637\">10.3390/e26080637</a>"},"abstract":[{"text":"Abstract\r\nMethods used in topological data analysis naturally capture higher-order interactions in point cloud data embedded in a metric space. This methodology was recently extended to data living in an information space, by which we mean a space measured with an information theoretical distance. One such setting is a finite collection of discrete probability distributions embedded in the probability simplex measured with the relative entropy (Kullback–Leibler divergence). More generally, one can work with a Bregman divergence parameterized by a different notion of entropy. While theoretical algorithms exist for this setup, there is a paucity of implementations for exploring and comparing geometric-topological properties of various information spaces. The interest of this work is therefore twofold. First, we propose the first robust algorithms and software for geometric and topological data analysis in information space. Perhaps surprisingly, despite working with Bregman divergences, our design reuses robust libraries for the Euclidean case. Second, using the new software, we take the first steps towards understanding the geometric-topological structure of these spaces. In particular, we compare them with the more familiar spaces equipped with the Euclidean and Fisher metrics.","lang":"eng"}],"oa_version":"Published Version","type":"journal_article","publication_identifier":{"eissn":["1099-4300"]},"status":"public","related_material":{"link":[{"url":"https://git.ista.ac.at/katharina.oelsboeck/wrap_2_3-public/","relation":"software"}]},"date_created":"2024-09-08T22:01:11Z","article_type":"original","year":"2024","oa":1,"publication_status":"published","doi":"10.3390/e26080637","file":[{"success":1,"file_id":"17948","date_created":"2024-09-09T09:01:12Z","file_name":"2024_Entropy_Edelsbrunner.pdf","access_level":"open_access","creator":"dernst","checksum":"624a9e2c5b49d6c38b88b0f675467ba3","content_type":"application/pdf","date_updated":"2024-09-09T09:01:12Z","relation":"main_file","file_size":8025139}],"intvolume":"        26","file_date_updated":"2024-09-09T09:01:12Z","ddc":["510"],"language":[{"iso":"eng"}],"author":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Katharina","last_name":"Ölsböck","orcid":"0000-0002-4672-8297","id":"4D4AA390-F248-11E8-B48F-1D18A9856A87","full_name":"Ölsböck, Katharina"},{"id":"379CA8B8-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Hubert","first_name":"Hubert","last_name":"Wagner"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"17891","department":[{"_id":"HeEd"}],"issue":"8","pmid":1,"publication":"Entropy","day":"01"},{"intvolume":"       293","publication_status":"published","oa":1,"doi":"10.4230/LIPIcs.SoCG.2024.87","file":[{"relation":"main_file","content_type":"application/pdf","date_updated":"2024-09-19T10:30:37Z","file_size":3507177,"file_name":"2024_LIPICs_Attali.pdf","access_level":"open_access","checksum":"9355c2e60b8ec285e1b22719c5b73f1a","creator":"dernst","success":1,"file_id":"18098","date_created":"2024-09-19T10:30:37Z"}],"project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"name":"Mathematics, Computer Science","call_identifier":"FWF","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","call_identifier":"FWF","name":"Persistence and stability of geometric complexes"},{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses"}],"ddc":["000"],"language":[{"iso":"eng"}],"author":[{"full_name":"Attali, Dominique","first_name":"Dominique","last_name":"Attali"},{"orcid":"0000-0001-7841-0091","last_name":"Kourimska","first_name":"Hana","full_name":"Kourimska, Hana","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E"},{"last_name":"Fillmore","first_name":"Christopher D","id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","full_name":"Fillmore, Christopher D"},{"last_name":"Ghosh","first_name":"Ishika","full_name":"Ghosh, Ishika","id":"ee449b28-344d-11ef-a6d5-9ca430e9e9ff"},{"last_name":"Lieutier","first_name":"Andre","full_name":"Lieutier, Andre"},{"first_name":"Elizabeth R","last_name":"Stephenson","orcid":"0000-0002-6862-208X","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","full_name":"Stephenson, Elizabeth R"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs"}],"file_date_updated":"2024-09-19T10:30:37Z","alternative_title":["LIPIcs"],"date_created":"2024-09-19T10:29:48Z","year":"2024","publication":"40th International Symposium on Computational Geometry","corr_author":"1","day":"06","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"18097","ec_funded":1,"department":[{"_id":"HeEd"}],"conference":{"end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2024-06-11","location":"Athens, Greece"},"month":"06","quality_controlled":"1","date_updated":"2025-04-15T07:16:58Z","date_published":"2024-06-06T00:00:00Z","article_processing_charge":"Yes","acknowledgement":"This research has been supported by the European Research Council (ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF), grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant No. I02979-N35. Mathijs Wintraecken: Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411, the Austrian science fund (FWF) grant No. M-3073, and the welcome package from IDEX of the Université Côte d’Azur.\r\nWe thank Jean-Daniel Boissonnat, Herbert Edelsbrunner, and Mariette Yvinec for discussion.","title":"The ultimate frontier: An optimality construction for homotopy inference (media exposition)","volume":293,"status":"public","type":"conference","publication_identifier":{"isbn":["9783959773164"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_number":"87","abstract":[{"lang":"eng","text":"In our companion paper \"Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds\" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting."}],"citation":{"ama":"Attali D, Kourimska H, Fillmore CD, et al. The ultimate frontier: An optimality construction for homotopy inference (media exposition). In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">10.4230/LIPIcs.SoCG.2024.87</a>","ieee":"D. Attali <i>et al.</i>, “The ultimate frontier: An optimality construction for homotopy inference (media exposition),” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","mla":"Attali, Dominique, et al. “The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition).” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 87, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">10.4230/LIPIcs.SoCG.2024.87</a>.","short":"D. Attali, H. Kourimska, C.D. Fillmore, I. Ghosh, A. Lieutier, E.R. Stephenson, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken M. 2024. The ultimate frontier: An optimality construction for homotopy inference (media exposition). 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 87.","apa":"Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson, E. R., &#38; Wintraecken, M. (2024). The ultimate frontier: An optimality construction for homotopy inference (media exposition). In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">https://doi.org/10.4230/LIPIcs.SoCG.2024.87</a>","chicago":"Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh, Andre Lieutier, Elizabeth R Stephenson, and Mathijs Wintraecken. “The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition).” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">https://doi.org/10.4230/LIPIcs.SoCG.2024.87</a>."},"oa_version":"Published Version"},{"related_material":{"record":[{"status":"public","id":"10828","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"11440","status":"public"},{"id":"18673","relation":"part_of_dissertation","status":"public"},{"id":"9345","relation":"part_of_dissertation","status":"public"}]},"type":"dissertation","publication_identifier":{"isbn":["978-3-99078-052-7"],"issn":["2663-337X"]},"status":"public","keyword":["persistent homology","topological data analysis","periodic","crystalline materials","images","fingerprint"],"citation":{"ieee":"T. Heiss, “New methods for applying topological data analysis to materials science,” Institute of Science and Technology Austria, 2024.","ama":"Heiss T. New methods for applying topological data analysis to materials science. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:18667\">10.15479/at:ista:18667</a>","chicago":"Heiss, Teresa. “New Methods for Applying Topological Data Analysis to Materials Science.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:18667\">https://doi.org/10.15479/at:ista:18667</a>.","apa":"Heiss, T. (2024). <i>New methods for applying topological data analysis to materials science</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:18667\">https://doi.org/10.15479/at:ista:18667</a>","short":"T. Heiss, New Methods for Applying Topological Data Analysis to Materials Science, Institute of Science and Technology Austria, 2024.","ista":"Heiss T. 2024. New methods for applying topological data analysis to materials science. Institute of Science and Technology Austria.","mla":"Heiss, Teresa. <i>New Methods for Applying Topological Data Analysis to Materials Science</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:18667\">10.15479/at:ista:18667</a>."},"abstract":[{"text":"Many chemical and physical properties of materials are determined by the material’s shape,\r\nfor example the size of its pores and the width of its tunnels. This makes materials science\r\na prime application area for geometrical and topological methods. Nevertheless many\r\nmethods in topological data analysis have not been satisfyingly extended to the needs of\r\nmaterials science. This thesis provides new methods and new mathematical theorems\r\ntargeted at those specific needs by answering four different research questions. While the\r\nmotivation for each of the research questions arises from materials science, the methods\r\nare versatile and can be applied in different areas as well. \r\n\r\nThe first research question is concerned with image data, for example a three-dimensional\r\ncomputed tomography (CT) scan of a material, like sand or stone. There are two commonly\r\nused topologies for digital images and depending on the application either of them might be\r\nrequired. However, software for computing the topological data analysis method persistence\r\nhomology, usually supports only one of the two topologies. We answer the question how to\r\ncompute persistent homology of an image with respect to one of the two topologies using\r\nsoftware that is intended for the other topology. \r\n\r\nThe second research question is concerned with image data as well, and asks how much\r\nof the topological information of an image is lost when the resolution is coarsened. As\r\ncomputer tomography scanners are more expensive the higher the resolution, it is an\r\nimportant question in materials science to know which resolution is enough to get satisfying\r\npersistent homology. We give theoretical bounds on the information loss based on different\r\ngeometrical properties of the object to be scanned. In addition, we conduct experiments on\r\nsand and stone CT image data. \r\n\r\nThe third research question is motivated by comparing crystalline materials efficiently. As\r\nthe atoms within a crystal repeat periodically, crystalline materials are either modeled by\r\nunmanageable infinite periodic point sets, or by one of their fundamental domains, which is\r\nunstable under perturbation. Therefore a fingerprint of crystalline materials is needed, with\r\nappropriate properties such that comparing the crystals can be eased by comparing the\r\nfingerprints instead. We define the density fingerprint and prove the necessary properties. \r\n\r\nThe fourth research question is motivated by studying the hole-structure or connectedness,\r\ni.e. persistent homology or merge trees, of crystalline materials. A common way to deal\r\nwith periodicity is to take a fundamental domain and identify opposite boundaries to form a\r\ntorus. However, computing persistent homology or merge trees on that torus loses some\r\nof the information materials scientists are interested in and is additionally not stable under\r\ncertain noise. We therefore decorate the merge tree stemming from the torus with additional\r\ninformation describing the density and growth rate of the periodic copies of a component\r\nwithin a growing spherical window. We prove all desired properties, like stability and efficient\r\ncomputability.","lang":"eng"}],"oa_version":"Published Version","publisher":"Institute of Science and Technology Austria","date_updated":"2026-07-07T13:43:27Z","month":"12","title":"New methods for applying topological data analysis to materials science","date_published":"2024-12-17T00:00:00Z","article_processing_charge":"No","acknowledgement":"I was supported by the European Research Council (ERC) Horizon 2020 project\r\n“Alpha Shape Theory Extended” No. 788183 and by the Pöttinger Scholarship. In addition,\r\nI am very thankful for having been able to attend the second Workshop for Women in\r\nComputational Topology in July 2019, funded by the Mathematical Sciences Institute at\r\nANU, the US National Science Foundation through the award CCF-1841455, the Australian\r\nMathematical Sciences Institute and the Association for Women in Mathematics. Two of the\r\nprojects presented in this thesis started there. One of them reached completion thanks to\r\nfunding from the MSRI Summer Research in Mathematics program awarded to me and my\r\ncollaborators in 2020.","day":"17","corr_author":"1","OA_place":"publisher","_id":"18667","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","department":[{"_id":"GradSch"},{"_id":"HeEd"}],"ec_funded":1,"page":"111","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","supervisor":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2024-12-19T10:24:50Z","degree_awarded":"PhD","ddc":["514","516","004"],"language":[{"iso":"eng"}],"author":[{"last_name":"Heiss","first_name":"Teresa","orcid":"0000-0002-1780-2689","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","full_name":"Heiss, Teresa"}],"publication_status":"published","oa":1,"project":[{"grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020"}],"doi":"10.15479/at:ista:18667","file":[{"success":1,"file_id":"18686","date_created":"2024-12-19T10:24:46Z","file_name":"Teresa_Heiss_PhD_Thesis_final.pdf","access_level":"open_access","creator":"theiss","checksum":"247bb057aed2fba1cd4711917aaa2d77","content_type":"application/pdf","date_updated":"2024-12-19T10:24:46Z","relation":"main_file","file_size":7752253},{"date_updated":"2024-12-19T10:24:50Z","relation":"source_file","content_type":"application/zip","file_size":17197731,"file_id":"18687","date_created":"2024-12-19T10:24:50Z","access_level":"closed","file_name":"PhD_Thesis.zip","creator":"theiss","checksum":"9648b45c07a008ee11a07f99856a139d"}],"year":"2024","date_created":"2024-12-17T16:17:55Z","alternative_title":["ISTA Thesis"]},{"arxiv":1,"article_processing_charge":"No","date_published":"2024-02-07T00:00:00Z","date_created":"2024-03-08T10:13:59Z","title":"Chromatic alpha complexes","year":"2024","month":"02","doi":"10.48550/arXiv.2212.03128","oa":1,"publication_status":"draft","date_updated":"2026-07-23T12:03:56Z","author":[{"full_name":"Cultrera di Montesano, Sebastiano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6249-0832","last_name":"Cultrera di Montesano","first_name":"Sebastiano"},{"id":"2B23F01E-F248-11E8-B48F-1D18A9856A87","full_name":"Draganov, Ondrej","last_name":"Draganov","first_name":"Ondrej","orcid":"0000-0003-0464-3823"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824","first_name":"Morteza","last_name":"Saghafian"}],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2212.03128"]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"main_file_link":[{"url":"https://arxiv.org/abs/2212.03128","open_access":"1"}],"oa_version":"Preprint","citation":{"chicago":"Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “Chromatic Alpha Complexes.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2212.03128\">https://doi.org/10.48550/arXiv.2212.03128</a>.","apa":"Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., &#38; Saghafian, M. (n.d.). Chromatic alpha complexes. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2212.03128\">https://doi.org/10.48550/arXiv.2212.03128</a>","short":"S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, ArXiv (n.d.).","ista":"Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. Chromatic alpha complexes. arXiv, 2212.03128.","mla":"Cultrera di Montesano, Sebastiano, et al. “Chromatic Alpha Complexes.” <i>ArXiv</i>, 2212.03128, doi:<a href=\"https://doi.org/10.48550/arXiv.2212.03128\">10.48550/arXiv.2212.03128</a>.","ieee":"S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “Chromatic alpha complexes,” <i>arXiv</i>. .","ama":"Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. Chromatic alpha complexes. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2212.03128\">10.48550/arXiv.2212.03128</a>"},"article_number":"2212.03128","abstract":[{"text":"Motivated by applications in the medical sciences, we study finite chromatic\r\nsets in Euclidean space from a topological perspective. Based on the persistent\r\nhomology for images, kernels and cokernels, we design provably stable\r\nhomological quantifiers that describe the geometric micro- and macro-structure\r\nof how the color classes mingle. These can be efficiently computed using\r\nchromatic variants of Delaunay and alpha complexes, and code that does these\r\ncomputations is provided.","lang":"eng"}],"department":[{"_id":"HeEd"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","_id":"15091","publication":"arXiv","status":"public","corr_author":"1","OA_place":"repository","type":"preprint","day":"07","related_material":{"record":[{"id":"18979","relation":"dissertation_contains","status":"public"},{"id":"15094","relation":"dissertation_contains","status":"public"},{"status":"public","relation":"later_version","id":"20585"}]}},{"author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János","first_name":"János","last_name":"Pach"}],"language":[{"iso":"eng"}],"ddc":["510"],"file_date_updated":"2024-06-17T08:46:33Z","intvolume":"       293","file":[{"file_size":766562,"date_updated":"2024-06-17T08:46:33Z","relation":"main_file","content_type":"application/pdf","date_created":"2024-06-17T08:46:33Z","success":1,"file_id":"17152","checksum":"5442d44fb89d77477a87668d6e61aac9","creator":"dernst","file_name":"2024_LIPICS_Edelsbrunner.pdf","access_level":"open_access"}],"doi":"10.4230/LIPIcs.SoCG.2024.53","project":[{"grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"name":"Persistence and stability of geometric complexes","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"},{"grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","call_identifier":"FWF"}],"oa":1,"publication_status":"published","year":"2024","alternative_title":["LIPIcs"],"date_created":"2024-06-16T22:01:06Z","day":"01","publication":"40th International Symposium on Computational Geometry","department":[{"_id":"HeEd"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14","start_date":"2024-06-11","location":"Athens, Greece"},"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"17146","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"quality_controlled":"1","date_updated":"2026-07-27T08:15:58Z","external_id":{"arxiv":["2310.14801"]},"month":"06","volume":293,"acknowledgement":"The first author is supported by the European Research Council (ERC), grant no. 788183, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant no. {I 02979-N35.} The second author is supported by the European Research Council (ERC), grant \"GeoScape\" and by the Hungarian Science Foundation (NKFIH), grant K-131529. Both authors are supported by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.\r\nThe authors thank Matt Kahle for communicating the question about extremal Čech complexes, Ben Schweinhart for early discussions on the linked circles construction in three dimensions, and Gábor Tardos for helpful remarks and suggestions.","date_published":"2024-06-01T00:00:00Z","article_processing_charge":"No","arxiv":1,"title":"Maximum Betti numbers of Čech complexes","related_material":{"record":[{"id":"20657","relation":"later_version","status":"public"}]},"status":"public","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773164"]},"type":"conference","oa_version":"Published Version","article_number":"53","citation":{"ama":"Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>","ieee":"H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","mla":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>.","short":"H. Edelsbrunner, J. Pach, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 53.","apa":"Edelsbrunner, H., &#38; Pach, J. (2024). Maximum Betti numbers of Čech complexes. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>","chicago":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>."},"scopus_import":"1","abstract":[{"lang":"eng","text":"The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p = O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions, which prove that this upper bound is asymptotically tight. For example, we describe a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of the Čech complex at the other radius is n². In particular, there is an arrangement of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"month":"01","external_id":{"pmid":["36687803"],"isi":["000846967100001"]},"quality_controlled":"1","date_updated":"2025-04-23T08:46:48Z","title":"A simple algorithm for higher-order Delaunay mosaics and alpha shapes","article_processing_charge":"Yes (via OA deal)","date_published":"2023-01-01T00:00:00Z","isi":1,"acknowledgement":"Open access funding provided by Austrian Science Fund (FWF). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.","volume":85,"type":"journal_article","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"status":"public","publisher":"Springer Nature","scopus_import":"1","citation":{"mla":"Edelsbrunner, Herbert, and Georg F. Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” <i>Algorithmica</i>, vol. 85, Springer Nature, 2023, pp. 277–95, doi:<a href=\"https://doi.org/10.1007/s00453-022-01027-6\">10.1007/s00453-022-01027-6</a>.","short":"H. Edelsbrunner, G.F. Osang, Algorithmica 85 (2023) 277–295.","ista":"Edelsbrunner H, Osang GF. 2023. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. 85, 277–295.","apa":"Edelsbrunner, H., &#38; Osang, G. F. (2023). A simple algorithm for higher-order Delaunay mosaics and alpha shapes. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-022-01027-6\">https://doi.org/10.1007/s00453-022-01027-6</a>","chicago":"Edelsbrunner, Herbert, and Georg F Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” <i>Algorithmica</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00453-022-01027-6\">https://doi.org/10.1007/s00453-022-01027-6</a>.","ama":"Edelsbrunner H, Osang GF. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. <i>Algorithmica</i>. 2023;85:277-295. doi:<a href=\"https://doi.org/10.1007/s00453-022-01027-6\">10.1007/s00453-022-01027-6</a>","ieee":"H. Edelsbrunner and G. F. Osang, “A simple algorithm for higher-order Delaunay mosaics and alpha shapes,” <i>Algorithmica</i>, vol. 85. Springer Nature, pp. 277–295, 2023."},"abstract":[{"text":"We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.","lang":"eng"}],"oa_version":"Published Version","publication_status":"published","oa":1,"doi":"10.1007/s00453-022-01027-6","file":[{"file_name":"2023_Algorithmica_Edelsbrunner.pdf","access_level":"open_access","checksum":"71685ca5121f4c837f40c3f8eb50c915","creator":"dernst","success":1,"file_id":"12322","date_created":"2023-01-20T10:02:48Z","date_updated":"2023-01-20T10:02:48Z","relation":"main_file","content_type":"application/pdf","file_size":911017}],"project":[{"grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"call_identifier":"FWF","name":"Mathematics, Computer Science","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes","call_identifier":"FWF"}],"intvolume":"        85","file_date_updated":"2023-01-20T10:02:48Z","language":[{"iso":"eng"}],"ddc":["510"],"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Osang, Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8882-5116","last_name":"Osang","first_name":"Georg F"}],"date_created":"2022-09-11T22:01:57Z","article_type":"original","year":"2023","corr_author":"1","publication":"Algorithmica","day":"01","page":"277-295","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12086","department":[{"_id":"HeEd"}],"ec_funded":1,"pmid":1},{"page":"156-191","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"department":[{"_id":"HeEd"}],"ec_funded":1,"_id":"12287","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","corr_author":"1","publication":"Discrete & Computational Geometry","day":"01","date_created":"2023-01-16T10:04:06Z","article_type":"original","year":"2023","doi":"10.1007/s00454-022-00431-7","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073"}],"file":[{"checksum":"46352e0ee71e460848f88685ca852681","creator":"dernst","file_name":"2023_DiscreteCompGeometry_Boissonnat.pdf","access_level":"open_access","date_created":"2023-02-02T11:01:10Z","success":1,"file_id":"12488","file_size":582850,"date_updated":"2023-02-02T11:01:10Z","relation":"main_file","content_type":"application/pdf"}],"oa":1,"publication_status":"published","intvolume":"        69","file_date_updated":"2023-02-02T11:01:10Z","author":[{"first_name":"Jean-Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean-Daniel"},{"first_name":"Ramsay","last_name":"Dyer","full_name":"Dyer, Ramsay"},{"first_name":"Arijit","last_name":"Ghosh","full_name":"Ghosh, Arijit"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"language":[{"iso":"eng"}],"ddc":["510"],"publisher":"Springer Nature","oa_version":"Published Version","scopus_import":"1","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"citation":{"apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., &#38; Wintraecken, M. (2023). Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>.","mla":"Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 156–91, doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>.","ista":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating general manifolds. Discrete &#38; Computational Geometry. 69, 156–191.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete &#38; Computational Geometry 69 (2023) 156–191.","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for triangulating general manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 69. Springer Nature, pp. 156–191, 2023.","ama":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. 2023;69:156-191. doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>"},"abstract":[{"text":"We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.","lang":"eng"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"type":"journal_article","status":"public","title":"Local criteria for triangulating general manifolds","isi":1,"acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian Science Fund (FWF): M-3073. A part of the results described in this paper were presented at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science Fund (FWF).","article_processing_charge":"No","date_published":"2023-01-01T00:00:00Z","volume":69,"month":"01","external_id":{"isi":["000862193600001"]},"quality_controlled":"1","date_updated":"2025-04-14T07:44:00Z"},{"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","page":"973-985","pmid":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12544","issue":"3","department":[{"_id":"HeEd"}],"ec_funded":1,"publication":"Journal of Chemical Information and Modeling","corr_author":"1","day":"13","article_type":"original","date_created":"2023-02-12T23:00:59Z","year":"2023","intvolume":"        63","publication_status":"published","oa":1,"doi":"10.1021/acs.jcim.2c01346","project":[{"grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","call_identifier":"FWF","name":"Mathematics, Computer Science"},{"call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"}],"file":[{"file_id":"14070","success":1,"date_created":"2023-08-16T12:21:13Z","access_level":"open_access","file_name":"2023_JCIM_Koehl.pdf","creator":"dernst","checksum":"7d20562269edff1e31b9d6019d4983b0","content_type":"application/pdf","relation":"main_file","date_updated":"2023-08-16T12:21:13Z","file_size":8069223}],"language":[{"iso":"eng"}],"ddc":["510","540"],"author":[{"last_name":"Koehl","first_name":"Patrice","full_name":"Koehl, Patrice"},{"orcid":"0000-0002-2548-617X","first_name":"Arseniy","last_name":"Akopyan","full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"}],"file_date_updated":"2023-08-16T12:21:13Z","publisher":"American Chemical Society","scopus_import":"1","citation":{"ieee":"P. Koehl, A. Akopyan, and H. Edelsbrunner, “Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives,” <i>Journal of Chemical Information and Modeling</i>, vol. 63, no. 3. American Chemical Society, pp. 973–985, 2023.","ama":"Koehl P, Akopyan A, Edelsbrunner H. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. <i>Journal of Chemical Information and Modeling</i>. 2023;63(3):973-985. doi:<a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">10.1021/acs.jcim.2c01346</a>","apa":"Koehl, P., Akopyan, A., &#38; Edelsbrunner, H. (2023). Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. <i>Journal of Chemical Information and Modeling</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">https://doi.org/10.1021/acs.jcim.2c01346</a>","chicago":"Koehl, Patrice, Arseniy Akopyan, and Herbert Edelsbrunner. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” <i>Journal of Chemical Information and Modeling</i>. American Chemical Society, 2023. <a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">https://doi.org/10.1021/acs.jcim.2c01346</a>.","mla":"Koehl, Patrice, et al. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” <i>Journal of Chemical Information and Modeling</i>, vol. 63, no. 3, American Chemical Society, 2023, pp. 973–85, doi:<a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">10.1021/acs.jcim.2c01346</a>.","ista":"Koehl P, Akopyan A, Edelsbrunner H. 2023. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. 63(3), 973–985.","short":"P. Koehl, A. Akopyan, H. Edelsbrunner, Journal of Chemical Information and Modeling 63 (2023) 973–985."},"abstract":[{"text":"Geometry is crucial in our efforts to comprehend the structures and dynamics of biomolecules. For example, volume, surface area, and integrated mean and Gaussian curvature of the union of balls representing a molecule are used to quantify its interactions with the water surrounding it in the morphometric implicit solvent models. The Alpha Shape theory provides an accurate and reliable method for computing these geometric measures. In this paper, we derive homogeneous formulas for the expressions of these measures and their derivatives with respect to the atomic coordinates, and we provide algorithms that implement them into a new software package, AlphaMol. The only variables in these formulas are the interatomic distances, making them insensitive to translations and rotations. AlphaMol includes a sequential algorithm and a parallel algorithm. In the parallel version, we partition the atoms of the molecule of interest into 3D rectangular blocks, using a kd-tree algorithm. We then apply the sequential algorithm of AlphaMol to each block, augmented by a buffer zone to account for atoms whose ball representations may partially cover the block. The current parallel version of AlphaMol leads to a 20-fold speed-up compared to an independent serial implementation when using 32 processors. For instance, it takes 31 s to compute the geometric measures and derivatives of each atom in a viral capsid with more than 26 million atoms on 32 Intel processors running at 2.7 GHz. The presence of the buffer zones, however, leads to redundant computations, which ultimately limit the impact of using multiple processors. AlphaMol is available as an OpenSource software.","lang":"eng"}],"oa_version":"Published Version","status":"public","type":"journal_article","publication_identifier":{"issn":["1549-9596"],"eissn":["1549-960X"]},"date_published":"2023-02-13T00:00:00Z","article_processing_charge":"No","isi":1,"acknowledgement":"P.K. acknowledges support from the University of California Multicampus Research Programs and Initiatives (Grant No. M21PR3267) and from the NSF (Grant No.1760485). H.E. acknowledges support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.\r\nOpen Access is funded by the Austrian Science Fund (FWF).","title":"Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives","volume":63,"month":"02","date_updated":"2025-04-15T07:16:52Z","quality_controlled":"1","external_id":{"pmid":["36638318"],"isi":["000920370700001"]}},{"file_date_updated":"2023-02-14T07:58:26Z","language":[{"iso":"eng"}],"ddc":["600"],"author":[{"full_name":"Forghani, Mohammad","first_name":"Mohammad","last_name":"Forghani"},{"full_name":"Claramunt, Christophe","last_name":"Claramunt","first_name":"Christophe"},{"orcid":"0000-0001-6746-4174","last_name":"Karimipour","first_name":"Farid","full_name":"Karimipour, Farid","id":"2A2BCDC4-CF62-11E9-BE5E-3B1EE6697425"},{"first_name":"Georg","last_name":"Heiler","full_name":"Heiler, Georg"}],"oa":1,"publication_status":"published","file":[{"date_updated":"2023-02-14T07:58:26Z","content_type":"application/pdf","relation":"main_file","file_size":1183339,"file_name":"Visual Analysis_Mobility_COVID19 - SocDM2022.pdf","access_level":"open_access","checksum":"c253bee25e6dfe484f96662daa119cb6","creator":"fkarimip","success":1,"file_id":"12549","date_created":"2023-02-14T07:58:26Z"}],"doi":"10.1109/icdmw58026.2022.00093","year":"2023","date_created":"2023-02-14T07:56:21Z","day":"08","publication":"2022 IEEE International Conference on Data Mining Workshops","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"12548","department":[{"_id":"HeEd"}],"conference":{"location":"Orlando, FL, United States","name":"ICDMW: Conference on Data Mining Workshops","end_date":"2022-12-01","start_date":"2022-11-28"},"has_accepted_license":"1","external_id":{"isi":["000971492200145"]},"date_updated":"2024-10-21T06:01:25Z","quality_controlled":"1","month":"02","title":"Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic","date_published":"2023-02-08T00:00:00Z","article_processing_charge":"No","isi":1,"type":"conference","publication_identifier":{"eisbn":["9798350346091"],"eissn":["2375-9259"]},"status":"public","abstract":[{"text":"The limited exchange between human communities is a key factor in preventing the spread of COVID-19. This paper introduces a digital framework that combines an integration of real mobility data at the country scale with a series of modeling techniques and visual capabilities that highlight mobility patterns before and during the pandemic. The findings not only significantly exhibit mobility trends and different degrees of similarities at regional and local levels but also provide potential insight into the emergence of a pandemic on human behavior patterns and their likely socio-economic impacts.","lang":"eng"}],"citation":{"ama":"Forghani M, Claramunt C, Karimipour F, Heiler G. Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic. In: <i>2022 IEEE International Conference on Data Mining Workshops</i>. Institute of Electrical and Electronics Engineers; 2023. doi:<a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">10.1109/icdmw58026.2022.00093</a>","ieee":"M. Forghani, C. Claramunt, F. Karimipour, and G. Heiler, “Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic,” in <i>2022 IEEE International Conference on Data Mining Workshops</i>, Orlando, FL, United States, 2023.","ista":"Forghani M, Claramunt C, Karimipour F, Heiler G. 2023. Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic. 2022 IEEE International Conference on Data Mining Workshops. ICDMW: Conference on Data Mining Workshops, 00093.","short":"M. Forghani, C. Claramunt, F. Karimipour, G. Heiler, in:, 2022 IEEE International Conference on Data Mining Workshops, Institute of Electrical and Electronics Engineers, 2023.","mla":"Forghani, Mohammad, et al. “Visual Analytics of Mobility Network Changes Observed Using Mobile Phone Data during COVID-19 Pandemic.” <i>2022 IEEE International Conference on Data Mining Workshops</i>, 00093, Institute of Electrical and Electronics Engineers, 2023, doi:<a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">10.1109/icdmw58026.2022.00093</a>.","chicago":"Forghani, Mohammad, Christophe Claramunt, Farid Karimipour, and Georg Heiler. “Visual Analytics of Mobility Network Changes Observed Using Mobile Phone Data during COVID-19 Pandemic.” In <i>2022 IEEE International Conference on Data Mining Workshops</i>. Institute of Electrical and Electronics Engineers, 2023. <a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">https://doi.org/10.1109/icdmw58026.2022.00093</a>.","apa":"Forghani, M., Claramunt, C., Karimipour, F., &#38; Heiler, G. (2023). Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic. In <i>2022 IEEE International Conference on Data Mining Workshops</i>. Orlando, FL, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">https://doi.org/10.1109/icdmw58026.2022.00093</a>"},"article_number":"00093","scopus_import":"1","oa_version":"Submitted Version","publisher":"Institute of Electrical and Electronics Engineers"},{"publisher":"Springer Nature","abstract":[{"text":"Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.","lang":"eng"}],"citation":{"ieee":"R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover bifiltration,” <i>Discrete and Computational Geometry</i>, vol. 70. Springer Nature, pp. 376–405, 2023.","ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. <i>Discrete and Computational Geometry</i>. 2023;70:376-405. doi:<a href=\"https://doi.org/10.1007/s00454-022-00476-8\">10.1007/s00454-022-00476-8</a>","apa":"Corbet, R., Kerber, M., Lesnick, M., &#38; Osang, G. F. (2023). Computing the multicover bifiltration. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00476-8\">https://doi.org/10.1007/s00454-022-00476-8</a>","chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00476-8\">https://doi.org/10.1007/s00454-022-00476-8</a>.","mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” <i>Discrete and Computational Geometry</i>, vol. 70, Springer Nature, 2023, pp. 376–405, doi:<a href=\"https://doi.org/10.1007/s00454-022-00476-8\">10.1007/s00454-022-00476-8</a>.","short":"R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, Discrete and Computational Geometry 70 (2023) 376–405.","ista":"Corbet R, Kerber M, Lesnick M, Osang GF. 2023. Computing the multicover bifiltration. Discrete and Computational Geometry. 70, 376–405."},"scopus_import":"1","oa_version":"Published Version","status":"public","type":"journal_article","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"related_material":{"record":[{"status":"public","id":"9605","relation":"earlier_version"}]},"arxiv":1,"article_processing_charge":"Yes (via OA deal)","date_published":"2023-09-01T00:00:00Z","isi":1,"acknowledgement":"We thank the anonymous reviewers for many helpful comments and suggestions, which led to substantial improvements of the paper. The first two authors were supported by the Austrian Science Fund (FWF) grant number P 29984-N35 and W1230. The first author was partly supported by an Austrian Marshall Plan Scholarship, and by the Brummer & Partners MathDataLab. A conference version of this paper was presented at the 37th International Symposium on Computational Geometry (SoCG 2021). Open access funding provided by the Royal Institute of Technology.","title":"Computing the multicover bifiltration","volume":70,"month":"09","date_updated":"2025-07-10T12:01:57Z","quality_controlled":"1","external_id":{"pmid":["37581017"],"isi":["000936496800001"],"arxiv":["2103.07823"]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","page":"376-405","pmid":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12709","department":[{"_id":"HeEd"}],"publication":"Discrete and Computational Geometry","day":"01","article_type":"original","date_created":"2023-03-05T23:01:06Z","year":"2023","intvolume":"        70","oa":1,"publication_status":"published","file":[{"date_created":"2023-03-07T14:40:14Z","file_id":"12715","success":1,"checksum":"71ce7e59f7ee4620acc704fecca620c2","creator":"cchlebak","access_level":"open_access","file_name":"2023_DisCompGeo_Corbet.pdf","file_size":1359323,"content_type":"application/pdf","date_updated":"2023-03-07T14:40:14Z","relation":"main_file"}],"doi":"10.1007/s00454-022-00476-8","ddc":["000"],"language":[{"iso":"eng"}],"author":[{"first_name":"René","last_name":"Corbet","full_name":"Corbet, René"},{"first_name":"Michael","last_name":"Kerber","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"},{"first_name":"Michael","last_name":"Lesnick","full_name":"Lesnick, Michael"},{"orcid":"0000-0002-8882-5116","first_name":"Georg F","last_name":"Osang","full_name":"Osang, Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2023-03-07T14:40:14Z"},{"oa":1,"publication_status":"published","doi":"10.1007/s41468-023-00116-x","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses"}],"intvolume":"         7","language":[{"iso":"eng"}],"author":[{"first_name":"Jean Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean Daniel"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs"}],"date_created":"2023-03-26T22:01:08Z","article_type":"original","year":"2023","corr_author":"1","publication":"Journal of Applied and Computational Topology","day":"01","page":"619-641","_id":"12763","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"department":[{"_id":"HeEd"}],"month":"09","quality_controlled":"1","date_updated":"2025-04-14T07:44:01Z","title":"The reach of subsets of manifolds","article_processing_charge":"No","date_published":"2023-09-01T00:00:00Z","acknowledgement":"We thank Eddie Aamari, David Cohen-Steiner, Isa Costantini, Fred Chazal, Ramsay Dyer, André Lieutier, and Alef Sterk for discussion and Pierre Pansu for encouragement. We further acknowledge the anonymous reviewers whose comments helped improve the exposition.\r\nThe research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions). The first author is further supported by the French government, through the 3IA Côte d’Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002. The second author is supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411 and the Austrian science fund (FWF) M-3073.","volume":7,"type":"journal_article","publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"status":"public","publisher":"Springer Nature","main_file_link":[{"url":"https://inserm.hal.science/INRIA-SACLAY/hal-04083524v1","open_access":"1"}],"scopus_import":"1","abstract":[{"lang":"eng","text":"Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift 176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert showed that sets of positive reach in Euclidean space and Riemannian manifolds are very similar. In this paper we introduce a slight variant of Kleinjohann’s and Bangert’s extension and quantify the similarity between sets of positive reach in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we bound the local feature size (a local version of the reach) of its lifting to the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated by the importance of the reach and local feature size to manifold learning, topological inference, and triangulating manifolds and the fact that intrinsic approaches circumvent the curse of dimensionality."}],"citation":{"chicago":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” <i>Journal of Applied and Computational Topology</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s41468-023-00116-x\">https://doi.org/10.1007/s41468-023-00116-x</a>.","apa":"Boissonnat, J. D., &#38; Wintraecken, M. (2023). The reach of subsets of manifolds. <i>Journal of Applied and Computational Topology</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s41468-023-00116-x\">https://doi.org/10.1007/s41468-023-00116-x</a>","short":"J.D. Boissonnat, M. Wintraecken, Journal of Applied and Computational Topology 7 (2023) 619–641.","ista":"Boissonnat JD, Wintraecken M. 2023. The reach of subsets of manifolds. Journal of Applied and Computational Topology. 7, 619–641.","mla":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” <i>Journal of Applied and Computational Topology</i>, vol. 7, Springer Nature, 2023, pp. 619–41, doi:<a href=\"https://doi.org/10.1007/s41468-023-00116-x\">10.1007/s41468-023-00116-x</a>.","ieee":"J. D. Boissonnat and M. Wintraecken, “The reach of subsets of manifolds,” <i>Journal of Applied and Computational Topology</i>, vol. 7. Springer Nature, pp. 619–641, 2023.","ama":"Boissonnat JD, Wintraecken M. The reach of subsets of manifolds. <i>Journal of Applied and Computational Topology</i>. 2023;7:619-641. doi:<a href=\"https://doi.org/10.1007/s41468-023-00116-x\">10.1007/s41468-023-00116-x</a>"},"oa_version":"Submitted Version"},{"pmid":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12764","department":[{"_id":"HeEd"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","page":"123-153","day":"01","publication":"Discrete and Computational Geometry","corr_author":"1","year":"2023","article_type":"original","date_created":"2023-03-26T22:01:09Z","language":[{"iso":"eng"}],"ddc":["510"],"author":[{"full_name":"Kourimska, Hana","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","orcid":"0000-0001-7841-0091","first_name":"Hana","last_name":"Kourimska"}],"file_date_updated":"2023-10-04T11:46:24Z","intvolume":"        70","oa":1,"publication_status":"published","doi":"10.1007/s00454-023-00484-2","file":[{"access_level":"open_access","file_name":"2023_DiscreteGeometry_Kourimska.pdf","checksum":"cdbf90ba4a7ddcb190d37b9e9d4cb9d3","creator":"dernst","file_id":"14396","success":1,"date_created":"2023-10-04T11:46:24Z","content_type":"application/pdf","relation":"main_file","date_updated":"2023-10-04T11:46:24Z","file_size":1026683}],"project":[{"grant_number":"I04245","_id":"26AD5D90-B435-11E9-9278-68D0E5697425","name":"Algebraic Footprints of Geometric Features in Homology","call_identifier":"FWF"}],"scopus_import":"1","abstract":[{"text":"We study a new discretization of the Gaussian curvature for polyhedral surfaces. This discrete Gaussian curvature is defined on each conical singularity of a polyhedral surface as the quotient of the angle defect and the area of the Voronoi cell corresponding to the singularity. We divide polyhedral surfaces into discrete conformal classes using a generalization of discrete conformal equivalence pioneered by Feng Luo. We subsequently show that, in every discrete conformal class, there exists a polyhedral surface with constant discrete Gaussian curvature. We also provide explicit examples to demonstrate that this surface is in general not unique.","lang":"eng"}],"citation":{"ama":"Kourimska H. Discrete yamabe problem for polyhedral surfaces. <i>Discrete and Computational Geometry</i>. 2023;70:123-153. doi:<a href=\"https://doi.org/10.1007/s00454-023-00484-2\">10.1007/s00454-023-00484-2</a>","ieee":"H. Kourimska, “Discrete yamabe problem for polyhedral surfaces,” <i>Discrete and Computational Geometry</i>, vol. 70. Springer Nature, pp. 123–153, 2023.","ista":"Kourimska H. 2023. Discrete yamabe problem for polyhedral surfaces. Discrete and Computational Geometry. 70, 123–153.","short":"H. Kourimska, Discrete and Computational Geometry 70 (2023) 123–153.","mla":"Kourimska, Hana. “Discrete Yamabe Problem for Polyhedral Surfaces.” <i>Discrete and Computational Geometry</i>, vol. 70, Springer Nature, 2023, pp. 123–53, doi:<a href=\"https://doi.org/10.1007/s00454-023-00484-2\">10.1007/s00454-023-00484-2</a>.","chicago":"Kourimska, Hana. “Discrete Yamabe Problem for Polyhedral Surfaces.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-023-00484-2\">https://doi.org/10.1007/s00454-023-00484-2</a>.","apa":"Kourimska, H. (2023). Discrete yamabe problem for polyhedral surfaces. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00484-2\">https://doi.org/10.1007/s00454-023-00484-2</a>"},"oa_version":"Published Version","publisher":"Springer Nature","status":"public","type":"journal_article","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"volume":70,"date_published":"2023-07-01T00:00:00Z","article_processing_charge":"Yes (via OA deal)","acknowledgement":"Open access funding provided by the Austrian Science Fund (FWF). This research was supported by the FWF grant, Project number I4245-N35, and by the Deutsche Forschungsgemeinschaft (DFG - German Research Foundation) - Project-ID 195170736 - TRR109.","isi":1,"title":"Discrete yamabe problem for polyhedral surfaces","quality_controlled":"1","date_updated":"2025-04-23T08:59:15Z","external_id":{"pmid":["37292248"],"isi":["000948148000001"]},"month":"07"},{"volume":24,"acknowledgement":"This work was begun at the University of Waterloo and was partially supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n","arxiv":1,"date_published":"2023-01-18T00:00:00Z","article_processing_charge":"No","title":"Token swapping on trees","quality_controlled":"1","date_updated":"2025-01-20T14:05:09Z","external_id":{"arxiv":["1903.06981"]},"month":"01","oa_version":"Published Version","article_number":"9","citation":{"ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. 2023;24(2). doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>","ieee":"A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2. EPI Sciences, 2023.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science 24 (2023).","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 24(2), 9.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (2023). Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences, 2023. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>."},"scopus_import":"1","abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"publisher":"EPI Sciences","related_material":{"record":[{"relation":"earlier_version","id":"7950","status":"public"}]},"status":"public","publication_identifier":{"issn":["1462-7264"],"eissn":["1365-8050"]},"type":"journal_article","year":"2023","article_type":"original","date_created":"2023-04-16T22:01:08Z","author":[{"full_name":"Biniaz, Ahmad","last_name":"Biniaz","first_name":"Ahmad"},{"full_name":"Jain, Kshitij","first_name":"Kshitij","last_name":"Jain"},{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","first_name":"Zuzana","last_name":"Masárová"},{"full_name":"Miltzow, Tillmann","first_name":"Tillmann","last_name":"Miltzow"},{"full_name":"Mondal, Debajyoti","first_name":"Debajyoti","last_name":"Mondal"},{"full_name":"Naredla, Anurag Murty","last_name":"Naredla","first_name":"Anurag Murty"},{"last_name":"Tkadlec","first_name":"Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef"},{"first_name":"Alexi","last_name":"Turcotte","full_name":"Turcotte, Alexi"}],"ddc":["000"],"language":[{"iso":"eng"}],"file_date_updated":"2023-04-17T08:10:28Z","intvolume":"        24","doi":"10.46298/DMTCS.8383","file":[{"relation":"main_file","date_updated":"2023-04-17T08:10:28Z","content_type":"application/pdf","file_size":2072197,"file_id":"12844","success":1,"date_created":"2023-04-17T08:10:28Z","access_level":"open_access","file_name":"2022_DMTCS_Biniaz.pdf","creator":"dernst","checksum":"439102ea4f6e2aeefd7107dfb9ccf532"}],"oa":1,"publication_status":"published","issue":"2","department":[{"_id":"KrCh"},{"_id":"HeEd"},{"_id":"UlWa"}],"_id":"12833","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"18","publication":"Discrete Mathematics and Theoretical Computer Science"},{"author":[{"last_name":"Lieutier","first_name":"André","full_name":"Lieutier, André"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"language":[{"iso":"eng"}],"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses"}],"doi":"10.1145/3564246.3585113","publication_status":"published","oa":1,"year":"2023","date_created":"2023-05-22T08:02:02Z","day":"02","corr_author":"1","publication":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing","department":[{"_id":"HeEd"}],"conference":{"location":"Orlando, FL, United States","name":"STOC: Symposium on Theory of Computing","end_date":"2023-06-23","start_date":"2023-06-20"},"ec_funded":1,"_id":"13048","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","page":"1768-1776","external_id":{"isi":["001064640700143"],"arxiv":["2303.04014"]},"quality_controlled":"1","date_updated":"2025-09-09T12:26:49Z","month":"06","title":"Hausdorff and Gromov-Hausdorff stable subsets of the medial axis","isi":1,"acknowledgement":"We are greatly indebted to Erin Chambers for posing a number of questions that eventually led to this paper. We would also like to thank the other organizers of the workshop on ‘Algorithms\r\nfor the medial axis’. We are also indebted to Tatiana Ezubova for helping with the search for and translation of Russian literature. The second author thanks all members of the Edelsbrunner and Datashape groups for the atmosphere in which the research was conducted.\r\nThe research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions). Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411. The Austrian science fund (FWF) M-3073.","article_processing_charge":"No","arxiv":1,"date_published":"2023-06-02T00:00:00Z","publication_identifier":{"isbn":["9781450399135"]},"type":"conference","status":"public","oa_version":"Preprint","abstract":[{"text":"In this paper we introduce a pruning of the medial axis called the (λ,α)-medial axis (axλα). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if K and K′ are close in the Hausdorff (dH) sense then the (λ,α)-medial axes of K and K′ are close as metric spaces, that is the Gromov-Hausdorff distance (dGH) between the two is 1/4-Hölder in the sense that dGH (axλα(K),axλα(K′)) ≲ dH(K,K′)1/4. The Hausdorff distance between the two medial axes is also bounded, by dH (axλα(K),λα(K′)) ≲ dH(K,K′)1/2. These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis.","lang":"eng"}],"scopus_import":"1","citation":{"ista":"Lieutier A, Wintraecken M. 2023. Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 1768–1776.","short":"A. Lieutier, M. Wintraecken, in:, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2023, pp. 1768–1776.","mla":"Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis.” <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2023, pp. 1768–76, doi:<a href=\"https://doi.org/10.1145/3564246.3585113\">10.1145/3564246.3585113</a>.","chicago":"Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis.” In <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>, 1768–76. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3564246.3585113\">https://doi.org/10.1145/3564246.3585113</a>.","apa":"Lieutier, A., &#38; Wintraecken, M. (2023). Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. In <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i> (pp. 1768–1776). Orlando, FL, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3564246.3585113\">https://doi.org/10.1145/3564246.3585113</a>","ama":"Lieutier A, Wintraecken M. Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. In: <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2023:1768-1776. doi:<a href=\"https://doi.org/10.1145/3564246.3585113\">10.1145/3564246.3585113</a>","ieee":"A. Lieutier and M. Wintraecken, “Hausdorff and Gromov-Hausdorff stable subsets of the medial axis,” in <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>, Orlando, FL, United States, 2023, pp. 1768–1776."},"publisher":"Association for Computing Machinery","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2303.04014"}]},{"volume":142,"acknowledgement":"The first author has been partially supported by the Ministry of Science, Technological Development and Innovation of the Republic of Serbia through the project no. 451-03-47/2023-01/200156. The fourth author is funded by the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35.","isi":1,"date_published":"2023-10-01T00:00:00Z","article_processing_charge":"No","title":"Discrete analytical objects in the body-centered cubic grid","quality_controlled":"1","date_updated":"2025-04-15T07:45:32Z","external_id":{"isi":["001013526000001"]},"month":"10","oa_version":"None","scopus_import":"1","abstract":[{"lang":"eng","text":"We propose a characterization of discrete analytical spheres, planes and lines in the body-centered cubic (BCC) grid, both in the Cartesian and in the recently proposed alternative compact coordinate system, in which each integer triplet addresses some voxel in the grid. We define spheres and planes through double Diophantine inequalities and investigate their relevant topological features, such as functionality or the interrelation between the thickness of the objects and their connectivity and separation properties. We define lines as the intersection of planes. The number of the planes (up to six) is equal to the number of the pairs of faces of a BCC voxel that are parallel to the line."}],"article_number":"109693","citation":{"ieee":"L. Čomić, G. Largeteau-Skapin, R. Zrour, R. Biswas, and E. Andres, “Discrete analytical objects in the body-centered cubic grid,” <i>Pattern Recognition</i>, vol. 142, no. 10. Elsevier, 2023.","ama":"Čomić L, Largeteau-Skapin G, Zrour R, Biswas R, Andres E. Discrete analytical objects in the body-centered cubic grid. <i>Pattern Recognition</i>. 2023;142(10). doi:<a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">10.1016/j.patcog.2023.109693</a>","chicago":"Čomić, Lidija, Gaëlle Largeteau-Skapin, Rita Zrour, Ranita Biswas, and Eric Andres. “Discrete Analytical Objects in the Body-Centered Cubic Grid.” <i>Pattern Recognition</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">https://doi.org/10.1016/j.patcog.2023.109693</a>.","apa":"Čomić, L., Largeteau-Skapin, G., Zrour, R., Biswas, R., &#38; Andres, E. (2023). Discrete analytical objects in the body-centered cubic grid. <i>Pattern Recognition</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">https://doi.org/10.1016/j.patcog.2023.109693</a>","ista":"Čomić L, Largeteau-Skapin G, Zrour R, Biswas R, Andres E. 2023. Discrete analytical objects in the body-centered cubic grid. Pattern Recognition. 142(10), 109693.","short":"L. Čomić, G. Largeteau-Skapin, R. Zrour, R. Biswas, E. Andres, Pattern Recognition 142 (2023).","mla":"Čomić, Lidija, et al. “Discrete Analytical Objects in the Body-Centered Cubic Grid.” <i>Pattern Recognition</i>, vol. 142, no. 10, 109693, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">10.1016/j.patcog.2023.109693</a>."},"publisher":"Elsevier","status":"public","publication_identifier":{"issn":["0031-3203"]},"type":"journal_article","year":"2023","article_type":"original","date_created":"2023-06-18T22:00:45Z","author":[{"first_name":"Lidija","last_name":"Čomić","full_name":"Čomić, Lidija"},{"first_name":"Gaëlle","last_name":"Largeteau-Skapin","full_name":"Largeteau-Skapin, Gaëlle"},{"last_name":"Zrour","first_name":"Rita","full_name":"Zrour, Rita"},{"id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","full_name":"Biswas, Ranita","first_name":"Ranita","last_name":"Biswas","orcid":"0000-0002-5372-7890"},{"full_name":"Andres, Eric","last_name":"Andres","first_name":"Eric"}],"language":[{"iso":"eng"}],"intvolume":"       142","doi":"10.1016/j.patcog.2023.109693","project":[{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","call_identifier":"FWF","name":"Persistence and stability of geometric complexes"},{"grant_number":"I4887","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","name":"Persistent Homology, Algorithms and Stochastic Geometry"}],"publication_status":"published","issue":"10","department":[{"_id":"HeEd"}],"_id":"13134","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","publication":"Pattern Recognition","corr_author":"1"},{"publication_status":"published","oa":1,"doi":"10.1016/j.jcta.2023.105776","file":[{"content_type":"application/pdf","relation":"main_file","date_updated":"2024-01-30T12:03:10Z","file_size":352555,"access_level":"open_access","file_name":"2023_JourCombinatiorialTheory_Fang.pdf","checksum":"9eebc213b4182a66063a99083ff5bd04","creator":"dernst","file_id":"14902","success":1,"date_created":"2024-01-30T12:03:10Z"}],"intvolume":"       199","file_date_updated":"2024-01-30T12:03:10Z","language":[{"iso":"eng"}],"ddc":["510"],"author":[{"last_name":"Fang","first_name":"Lixing","full_name":"Fang, Lixing"},{"full_name":"Huang, Hao","first_name":"Hao","last_name":"Huang"},{"id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"full_name":"Tardos, Gábor","first_name":"Gábor","last_name":"Tardos"},{"last_name":"Zuo","first_name":"Junchi","full_name":"Zuo, Junchi"}],"date_created":"2023-06-25T22:00:45Z","article_type":"original","year":"2023","corr_author":"1","publication":"Journal of Combinatorial Theory. Series A","day":"01","tmp":{"name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)"},"has_accepted_license":"1","_id":"13165","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","issue":"10","department":[{"_id":"HeEd"}],"month":"10","external_id":{"arxiv":["2206.13592"],"isi":["001144487800001"]},"license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","date_updated":"2025-09-09T12:30:39Z","quality_controlled":"1","title":"Successive vertex orderings of fully regular graphs","arxiv":1,"article_processing_charge":"Yes (in subscription journal)","date_published":"2023-10-01T00:00:00Z","isi":1,"volume":199,"type":"journal_article","publication_identifier":{"issn":["0097-3165"],"eissn":["1096-0899"]},"status":"public","publisher":"Elsevier","citation":{"ama":"Fang L, Huang H, Pach J, Tardos G, Zuo J. Successive vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory Series A</i>. 2023;199(10). doi:<a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">10.1016/j.jcta.2023.105776</a>","ieee":"L. Fang, H. Huang, J. Pach, G. Tardos, and J. Zuo, “Successive vertex orderings of fully regular graphs,” <i>Journal of Combinatorial Theory. Series A</i>, vol. 199, no. 10. Elsevier, 2023.","mla":"Fang, Lixing, et al. “Successive Vertex Orderings of Fully Regular Graphs.” <i>Journal of Combinatorial Theory. Series A</i>, vol. 199, no. 10, 105776, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">10.1016/j.jcta.2023.105776</a>.","ista":"Fang L, Huang H, Pach J, Tardos G, Zuo J. 2023. Successive vertex orderings of fully regular graphs. Journal of Combinatorial Theory. Series A. 199(10), 105776.","short":"L. Fang, H. Huang, J. Pach, G. Tardos, J. Zuo, Journal of Combinatorial Theory. Series A 199 (2023).","apa":"Fang, L., Huang, H., Pach, J., Tardos, G., &#38; Zuo, J. (2023). Successive vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory. Series A</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">https://doi.org/10.1016/j.jcta.2023.105776</a>","chicago":"Fang, Lixing, Hao Huang, János Pach, Gábor Tardos, and Junchi Zuo. “Successive Vertex Orderings of Fully Regular Graphs.” <i>Journal of Combinatorial Theory. Series A</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">https://doi.org/10.1016/j.jcta.2023.105776</a>."},"article_number":"105776","scopus_import":"1","abstract":[{"text":"A graph G=(V, E) is called fully regular if for every independent set I c V, the number of vertices in V\\I  that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph.\r\nAs an application of our results, we give alternative proofs of two theorems of Stanley and Gao & Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph.\r\nAs another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small.","lang":"eng"}],"oa_version":"Published Version"}]