--- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '20456' abstract: - lang: eng text: Given a locally finite set A⊆Rd and a coloring χ:A→{0,1,…,s}, we introduce the chromatic Delaunay mosaic of χ, which is a Delaunay mosaic in Rs+d that represents how points of different colors mingle. Our main results are bounds on the size of the chromatic Delaunay mosaic, in which we assume that d and s are constants. For example, if A is finite with n=#A, and the coloring is random, then the chromatic Delaunay mosaic has O(n⌈d/2⌉) cells in expectation. In contrast, for Delone sets and Poisson point processes in Rd, the expected number of cells within a closed ball is only a constant times the number of points in this ball. Furthermore, in R2 all colorings of a dense set of n points have chromatic Delaunay mosaics of size O(n). This encourages the use of chromatic Delaunay mosaics in applications. acknowledgement: The fourth author thanks Boris Aronov for insightful discussions on the size of the overlay of Voronoi tessellations. Open access funding provided by Institute of Science and Technology (IST Austria). 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. article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Ranita full_name: Biswas, Ranita id: 3C2B033E-F248-11E8-B48F-1D18A9856A87 last_name: Biswas orcid: 0000-0002-5372-7890 - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 - first_name: Ondrej full_name: Draganov, Ondrej id: 2B23F01E-F248-11E8-B48F-1D18A9856A87 last_name: Draganov orcid: 0000-0003-0464-3823 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: Biswas R, Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry. 2026;75:24-47. doi:10.1007/s00454-025-00778-7 apa: Biswas, R., Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (2026). On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-025-00778-7 chicago: Biswas, Ranita, Sebastiano Cultrera di Montesano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “On the Size of Chromatic Delaunay Mosaics.” Discrete and Computational Geometry. Springer Nature, 2026. https://doi.org/10.1007/s00454-025-00778-7. ieee: R. Biswas, S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “On the size of chromatic Delaunay mosaics,” Discrete and Computational Geometry, vol. 75. Springer Nature, pp. 24–47, 2026. ista: Biswas R, Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2026. On the size of chromatic Delaunay mosaics. Discrete and Computational Geometry. 75, 24–47. mla: Biswas, Ranita, et al. “On the Size of Chromatic Delaunay Mosaics.” Discrete and Computational Geometry, vol. 75, Springer Nature, 2026, pp. 24–47, doi:10.1007/s00454-025-00778-7. short: R. Biswas, S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, Discrete and Computational Geometry 75 (2026) 24–47. corr_author: '1' date_created: 2025-10-12T22:01:26Z date_published: 2026-01-01T00:00:00Z date_updated: 2026-01-05T13:21:56Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.1007/s00454-025-00778-7 ec_funded: 1 external_id: arxiv: - '2212.03121' isi: - '001584166900001' file: - access_level: open_access checksum: 0addb5c1b78142f9fb453bfa04695400 content_type: application/pdf creator: dernst date_created: 2026-01-05T13:21:20Z date_updated: 2026-01-05T13:21:20Z file_id: '20952' file_name: 2026_DiscreteCompGeom_Biswas.pdf file_size: 570922 relation: main_file success: 1 file_date_updated: 2026-01-05T13:21:20Z has_accepted_license: '1' intvolume: ' 75' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: 24-47 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Discrete and Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '15090' relation: earlier_version status: public scopus_import: '1' status: public title: On the size of chromatic Delaunay mosaics tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 75 year: '2026' ... --- OA_place: repository OA_type: green _id: '21410' abstract: - lang: eng text: Given a finite set of red and blue points in R^d, the MST-ratio is defined as the total length of the Euclidean minimum spanning trees of the red points and the blue points, divided by the length of the Euclidean minimum spanning tree of their union. The MST-ratio has recently gained attention due to its direct interpretation in topological models for studying point sets with applications in spatial biology. The maximum MST-ratio of a point set is the maximum MST-ratio over all proper colorings of its points by red and blue. We prove that finding the maximum MST-ratio of a given point set is NP-hard when the dimension is part of the input. Moreover, we present a quadratic-time 3-approximation algorithm for this problem. As part of the proof, we show that in any metric space, the maximum MST-ratio is smaller than 3. Furthermore, we study the average MST-ratio over all colorings of a set of n points. We show that this average is always at least n-2/n-1, and for n random points uniformly distributed in a d-dimensional unit cube, the average tends to (math formular) in expectation as n approaches infinity. acknowledgement: "A. J. Ameli—Supported by the project COALESCE (ERC grant no. 853234).\r\nM. Saghafian—Partially supported by the European Research Council (ERC), grant no. 788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31." alternative_title: - LNCS article_processing_charge: No arxiv: 1 author: - first_name: Afrouz full_name: Jabal Ameli, Afrouz last_name: Jabal Ameli - first_name: Faezeh full_name: Motiei, Faezeh last_name: Motiei - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: 'Jabal Ameli A, Motiei F, Saghafian M. On the MST-ratio: Theoretical bounds and complexity of finding the maximum. In: 20th International Conference and Workshops on Algorithms and Computation. Vol 16444. Springer Nature; 2026:386-401. doi:10.1007/978-981-95-7127-7_26' apa: 'Jabal Ameli, A., Motiei, F., & Saghafian, M. (2026). On the MST-ratio: Theoretical bounds and complexity of finding the maximum. In 20th International Conference and Workshops on Algorithms and Computation (Vol. 16444, pp. 386–401). Perugia, Italy: Springer Nature. https://doi.org/10.1007/978-981-95-7127-7_26' chicago: 'Jabal Ameli, Afrouz, Faezeh Motiei, and Morteza Saghafian. “On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum.” In 20th International Conference and Workshops on Algorithms and Computation, 16444:386–401. Springer Nature, 2026. https://doi.org/10.1007/978-981-95-7127-7_26.' ieee: 'A. Jabal Ameli, F. Motiei, and M. Saghafian, “On the MST-ratio: Theoretical bounds and complexity of finding the maximum,” in 20th International Conference and Workshops on Algorithms and Computation, Perugia, Italy, 2026, vol. 16444, pp. 386–401.' ista: 'Jabal Ameli A, Motiei F, Saghafian M. 2026. On the MST-ratio: Theoretical bounds and complexity of finding the maximum. 20th International Conference and Workshops on Algorithms and Computation. WALCOM: International Conference and Workshops on Algorithms and Computation, LNCS, vol. 16444, 386–401.' mla: 'Jabal Ameli, Afrouz, et al. “On the MST-Ratio: Theoretical Bounds and Complexity of Finding the Maximum.” 20th International Conference and Workshops on Algorithms and Computation, vol. 16444, Springer Nature, 2026, pp. 386–401, doi:10.1007/978-981-95-7127-7_26.' short: A. Jabal Ameli, F. Motiei, M. Saghafian, in:, 20th International Conference and Workshops on Algorithms and Computation, Springer Nature, 2026, pp. 386–401. conference: end_date: 2026-03-06 location: Perugia, Italy name: 'WALCOM: International Conference and Workshops on Algorithms and Computation' start_date: 2026-03-04 date_created: 2026-03-08T23:01:45Z date_published: 2026-02-14T00:00:00Z date_updated: 2026-03-09T10:25:41Z day: '14' department: - _id: HeEd doi: 10.1007/978-981-95-7127-7_26 ec_funded: 1 external_id: arxiv: - '2409.11079' intvolume: ' 16444' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2409.11079 month: '02' oa: 1 oa_version: Preprint page: 386-401 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science publication: 20th International Conference and Workshops on Algorithms and Computation publication_identifier: eissn: - 1611-3349 isbn: - '9789819571260' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: 'On the MST-ratio: Theoretical bounds and complexity of finding the maximum' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 16444 year: '2026' ... --- OA_place: repository OA_type: green _id: '18626' abstract: - lang: eng text: "The local angle property of the (order-1) Delaunay triangulations of a generic set in R2\r\n asserts that the sum of two angles opposite a common edge is less than π. This paper extends this property to higher order and uses it to generalize two classic properties from order-1 to order-2: (1) among the complete level-2 hypertriangulations of a generic point set in R2, the order-2 Delaunay triangulation lexicographically maximizes the sorted angle vector; (2) among the maximal level-2 hypertriangulations of a generic point set in R2, the order-2 Delaunay triangulation is the only one that has the local angle property. We also use our method of establishing (2) to give a new short proof of the angle vector optimality for the (order-1) Delaunay triangulation. For order-1, both properties have been instrumental in numerous applications of Delaunay triangulations, and we expect that their generalization will make order-2 Delaunay triangulations more attractive to applications as well." acknowledgement: Work by the first and third authors is partially 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. I 02979-N35. Work by the second author is partially supported by the Alexander von Humboldt Foundation. article_number: '110055' article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Alexey full_name: Garber, Alexey last_name: Garber - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: Edelsbrunner H, Garber A, Saghafian M. Order-2 Delaunay triangulations optimize angles. Advances in Mathematics. 2025;461. doi:10.1016/j.aim.2024.110055 apa: Edelsbrunner, H., Garber, A., & Saghafian, M. (2025). Order-2 Delaunay triangulations optimize angles. Advances in Mathematics. Elsevier. https://doi.org/10.1016/j.aim.2024.110055 chicago: Edelsbrunner, Herbert, Alexey Garber, and Morteza Saghafian. “Order-2 Delaunay Triangulations Optimize Angles.” Advances in Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.aim.2024.110055. ieee: H. Edelsbrunner, A. Garber, and M. Saghafian, “Order-2 Delaunay triangulations optimize angles,” Advances in Mathematics, vol. 461. Elsevier, 2025. ista: Edelsbrunner H, Garber A, Saghafian M. 2025. Order-2 Delaunay triangulations optimize angles. Advances in Mathematics. 461, 110055. mla: Edelsbrunner, Herbert, et al. “Order-2 Delaunay Triangulations Optimize Angles.” Advances in Mathematics, vol. 461, 110055, Elsevier, 2025, doi:10.1016/j.aim.2024.110055. short: H. Edelsbrunner, A. Garber, M. Saghafian, Advances in Mathematics 461 (2025). corr_author: '1' date_created: 2024-12-08T23:01:54Z date_published: 2025-02-01T00:00:00Z date_updated: 2025-04-15T07:16:53Z day: '01' department: - _id: HeEd doi: 10.1016/j.aim.2024.110055 ec_funded: 1 external_id: arxiv: - '2310.18238' isi: - '001370682500001' intvolume: ' 461' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2310.18238 month: '02' oa: 1 oa_version: Preprint project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Advances in Mathematics publication_identifier: eissn: - 1090-2082 issn: - 0001-8708 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Order-2 Delaunay triangulations optimize angles type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 461 year: '2025' ... --- OA_type: closed access _id: '19937' abstract: - lang: eng text: Simplets are elementary units within simplicial complexes and are fundamental for analyzing the structure of simplicial complexes. Previous efforts have mainly focused on accurately counting or approximating the number of simplets rather than studying their frequencies. However, analyzing simplet frequencies is more practical for large-scale simplicial complexes. This paper introduces the Simplet Frequency Distribution (SFD) vector, which enables the analysis of simplet frequencies in simplicial complexes. Additionally, we provide a bound on the sample complexity required to approximate the SFD vector using any uniform sampling-based algorithm accurately. We extend the definition of simplet frequency distribution to encompass simplices, allowing for the analysis of simplet frequencies within simplices of simplicial complexes. This paper introduces the Simplet Degree Vector (SDV) and the Simplet Degree Centrality (SDC), facilitating this analysis for each simplex. Furthermore, we present a bound on the sample complexity required for accurately approximating the SDV and SDC for a set of simplices using any uniform sampling-based algorithm. We also introduce algorithms for approximating SFD, geometric SFD, SDV, and SDC. We also validate the theoretical bounds with experiments on random simplicial complexes and demonstrate the practical application through a case study. acknowledgement: "The authors would like to thank the anonymous reviewers for their valuable comments and suggestions, which improved this paper.\r\nWork by the first and fourth authors is partially 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. I 02979-N35." article_number: '122425' article_processing_charge: No article_type: original author: - first_name: Mohammad full_name: Mahini, Mohammad last_name: Mahini - first_name: Hamid full_name: Beigy, Hamid last_name: Beigy - first_name: Salman full_name: Qadami, Salman last_name: Qadami - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: 'Mahini M, Beigy H, Qadami S, Saghafian M. Simplet-based signatures and approximation in simplicial complexes: Frequency, degree, and centrality. Information Sciences. 2025;719(11). doi:10.1016/j.ins.2025.122425' apa: 'Mahini, M., Beigy, H., Qadami, S., & Saghafian, M. (2025). Simplet-based signatures and approximation in simplicial complexes: Frequency, degree, and centrality. Information Sciences. Elsevier. https://doi.org/10.1016/j.ins.2025.122425' chicago: 'Mahini, Mohammad, Hamid Beigy, Salman Qadami, and Morteza Saghafian. “Simplet-Based Signatures and Approximation in Simplicial Complexes: Frequency, Degree, and Centrality.” Information Sciences. Elsevier, 2025. https://doi.org/10.1016/j.ins.2025.122425.' ieee: 'M. Mahini, H. Beigy, S. Qadami, and M. Saghafian, “Simplet-based signatures and approximation in simplicial complexes: Frequency, degree, and centrality,” Information Sciences, vol. 719, no. 11. Elsevier, 2025.' ista: 'Mahini M, Beigy H, Qadami S, Saghafian M. 2025. Simplet-based signatures and approximation in simplicial complexes: Frequency, degree, and centrality. Information Sciences. 719(11), 122425.' mla: 'Mahini, Mohammad, et al. “Simplet-Based Signatures and Approximation in Simplicial Complexes: Frequency, Degree, and Centrality.” Information Sciences, vol. 719, no. 11, 122425, Elsevier, 2025, doi:10.1016/j.ins.2025.122425.' short: M. Mahini, H. Beigy, S. Qadami, M. Saghafian, Information Sciences 719 (2025). corr_author: '1' date_created: 2025-06-30T08:48:48Z date_published: 2025-11-01T00:00:00Z date_updated: 2025-12-30T09:05:32Z day: '01' department: - _id: HeEd doi: 10.1016/j.ins.2025.122425 ec_funded: 1 external_id: isi: - '001516170500002' intvolume: ' 719' isi: 1 issue: '11' language: - iso: eng month: '11' oa_version: None project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Information Sciences publication_identifier: issn: - 0020-0255 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: 'Simplet-based signatures and approximation in simplicial complexes: Frequency, degree, and centrality' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 719 year: '2025' ... --- DOAJ_listed: '1' OA_place: publisher OA_type: gold PlanS_conform: '1' _id: '20293' abstract: - lang: eng text: Motivated by questions arising at the intersection of information theory and geometry, we compare two dissimilarity measures between finite categorical distributions. One is the well-known Jensen–Shannon divergence, which is easy to compute and whose square root is a proper metric. The other is what we call the minmax divergence, which is harder to compute. Just like the Jensen–Shannon divergence, it arises naturally from the Kullback–Leibler divergence. The main contribution of this paper is a proof showing that the minmax divergence can be tightly approximated by the Jensen–Shannon divergence. The bounds suggest that the square root of the minmax divergence is a metric, and we prove that this is indeed true in the one-dimensional case. The general case remains open. Finally, we consider analogous questions in the context of another Bregman divergence and the corresponding Burbea–Rao (Jensen–Bregman) divergence. acknowledgement: "This research received partial funding from the European Research Council (ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme, grant no. 788183, the\r\nWittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, the DFG Collaborative\r\nResearch Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35, and the 2022 Google Research Scholar Award for project ‘Algorithms for Topological Analysis of Neural Networks’. The APC was waived." article_number: '854' article_processing_charge: Yes article_type: original author: - first_name: Arseniy full_name: Akopyan, Arseniy id: 430D2C90-F248-11E8-B48F-1D18A9856A87 last_name: Akopyan orcid: 0000-0002-2548-617X - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Ziga full_name: Virk, Ziga id: 2E36B656-F248-11E8-B48F-1D18A9856A87 last_name: Virk - first_name: Hubert full_name: Wagner, Hubert id: 379CA8B8-F248-11E8-B48F-1D18A9856A87 last_name: Wagner citation: ama: Akopyan A, Edelsbrunner H, Virk Z, Wagner H. Tight bounds between the Jensen–Shannon divergence and the minmax divergence. Entropy. 2025;27(8). doi:10.3390/e27080854 apa: Akopyan, A., Edelsbrunner, H., Virk, Z., & Wagner, H. (2025). Tight bounds between the Jensen–Shannon divergence and the minmax divergence. Entropy. MDPI. https://doi.org/10.3390/e27080854 chicago: Akopyan, Arseniy, Herbert Edelsbrunner, Ziga Virk, and Hubert Wagner. “Tight Bounds between the Jensen–Shannon Divergence and the Minmax Divergence.” Entropy. MDPI, 2025. https://doi.org/10.3390/e27080854. ieee: A. Akopyan, H. Edelsbrunner, Z. Virk, and H. Wagner, “Tight bounds between the Jensen–Shannon divergence and the minmax divergence,” Entropy, vol. 27, no. 8. MDPI, 2025. ista: Akopyan A, Edelsbrunner H, Virk Z, Wagner H. 2025. Tight bounds between the Jensen–Shannon divergence and the minmax divergence. Entropy. 27(8), 854. mla: Akopyan, Arseniy, et al. “Tight Bounds between the Jensen–Shannon Divergence and the Minmax Divergence.” Entropy, vol. 27, no. 8, 854, MDPI, 2025, doi:10.3390/e27080854. short: A. Akopyan, H. Edelsbrunner, Z. Virk, H. Wagner, Entropy 27 (2025). corr_author: '1' date_created: 2025-09-07T22:01:33Z date_published: 2025-08-01T00:00:00Z date_updated: 2025-09-30T14:32:31Z day: '01' ddc: - '500' department: - _id: HeEd doi: 10.3390/e27080854 ec_funded: 1 external_id: isi: - '001557476000001' pmid: - '40870326' file: - access_level: open_access checksum: 65c5399c4015d9c8abb8c7a96f3d7836 content_type: application/pdf creator: dernst date_created: 2025-09-08T07:55:48Z date_updated: 2025-09-08T07:55:48Z file_id: '20309' file_name: 2025_Entropy_Akopyan.pdf file_size: 379340 relation: main_file success: 1 file_date_updated: 2025-09-08T07:55:48Z has_accepted_license: '1' intvolume: ' 27' isi: 1 issue: '8' language: - iso: eng month: '08' oa: 1 oa_version: Published Version pmid: 1 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Entropy publication_identifier: eissn: - 1099-4300 publication_status: published publisher: MDPI quality_controlled: '1' scopus_import: '1' status: public title: Tight bounds between the Jensen–Shannon divergence and the minmax divergence tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 27 year: '2025' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '20323' 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. acknowledgement: 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. Z342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35 article_number: '108068' article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Adam full_name: Brown, Adam id: 70B7FDF6-608D-11E9-9333-8535E6697425 last_name: Brown - first_name: Ondrej full_name: Draganov, Ondrej id: 2B23F01E-F248-11E8-B48F-1D18A9856A87 last_name: Draganov orcid: 0000-0003-0464-3823 citation: ama: Brown A, Draganov O. Discrete microlocal Morse theory. Journal of Pure and Applied Algebra. 2025;229(10). doi:10.1016/j.jpaa.2025.108068 apa: Brown, A., & Draganov, O. (2025). Discrete microlocal Morse theory. Journal of Pure and Applied Algebra. Elsevier. https://doi.org/10.1016/j.jpaa.2025.108068 chicago: Brown, Adam, and Ondrej Draganov. “Discrete Microlocal Morse Theory.” Journal of Pure and Applied Algebra. Elsevier, 2025. https://doi.org/10.1016/j.jpaa.2025.108068. ieee: A. Brown and O. Draganov, “Discrete microlocal Morse theory,” Journal of Pure and Applied Algebra, vol. 229, no. 10. Elsevier, 2025. ista: Brown A, Draganov O. 2025. Discrete microlocal Morse theory. Journal of Pure and Applied Algebra. 229(10), 108068. mla: Brown, Adam, and Ondrej Draganov. “Discrete Microlocal Morse Theory.” Journal of Pure and Applied Algebra, vol. 229, no. 10, 108068, Elsevier, 2025, doi:10.1016/j.jpaa.2025.108068. short: A. Brown, O. Draganov, Journal of Pure and Applied Algebra 229 (2025). corr_author: '1' date_created: 2025-09-10T05:40:09Z date_published: 2025-10-01T00:00:00Z date_updated: 2025-12-30T07:55:21Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.1016/j.jpaa.2025.108068 ec_funded: 1 external_id: arxiv: - '2209.14993' file: - access_level: open_access checksum: 39bcad462278c9322ef810af7db67f56 content_type: application/pdf creator: dernst date_created: 2025-12-30T07:55:08Z date_updated: 2025-12-30T07:55:08Z file_id: '20886' file_name: 2025_JourPureAppliedAlgebra_Brown.pdf file_size: 3090836 relation: main_file success: 1 file_date_updated: 2025-12-30T07:55:08Z has_accepted_license: '1' intvolume: ' 229' issue: '10' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Journal of Pure and Applied Algebra publication_identifier: issn: - 0022-4049 publication_status: published publisher: Elsevier quality_controlled: '1' related_material: record: - id: '18981' relation: earlier_version status: public scopus_import: '1' status: public title: Discrete microlocal Morse theory tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 229 year: '2025' ... --- OA_place: repository OA_type: green _id: '20490' abstract: - lang: eng text: "We study flips in hypertriangulations of planar points sets. Here a level-k hypertriangulation of n\r\n points in the plane is a subdivision induced by the projection of a k-hypersimplex, which is the convex hull of the barycenters of the (k-1)-dimensional faces of the standard (n-1)-simplex. In particular, we introduce four types of flips and prove that the level-2 hypertriangulations are connected by these flips.\r\n" acknowledgement: Work by all authors but the second is 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. I 02979-N35. Work by the second author is partially supported by the Alexander von Humboldt Foundation and by the Simons Foundation . The second author thanks Jesús A. De Loera for useful discussions on flips and non-flips and Pavel Galashin and Alexey Balitskiy for useful discussions on plabic graphs. article_number: '104248' article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Alexey full_name: Garber, Alexey last_name: Garber - first_name: Mohadese full_name: Ghafari, Mohadese last_name: Ghafari - first_name: Teresa full_name: Heiss, Teresa id: 4879BB4E-F248-11E8-B48F-1D18A9856A87 last_name: Heiss orcid: 0000-0002-1780-2689 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. Flips in two-dimensional hypertriangulations. European Journal of Combinatorics. 2025;132. doi:10.1016/j.ejc.2025.104248 apa: Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., & Saghafian, M. (2025). Flips in two-dimensional hypertriangulations. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104248 chicago: Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafari, Teresa Heiss, and Morteza Saghafian. “Flips in Two-Dimensional Hypertriangulations.” European Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104248. ieee: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, and M. Saghafian, “Flips in two-dimensional hypertriangulations,” European Journal of Combinatorics, vol. 132. Elsevier, 2025. ista: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2025. Flips in two-dimensional hypertriangulations. European Journal of Combinatorics. 132, 104248. mla: Edelsbrunner, Herbert, et al. “Flips in Two-Dimensional Hypertriangulations.” European Journal of Combinatorics, vol. 132, 104248, Elsevier, 2025, doi:10.1016/j.ejc.2025.104248. short: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, European Journal of Combinatorics 132 (2025). corr_author: '1' date_created: 2025-10-19T22:01:31Z date_published: 2025-10-10T00:00:00Z date_updated: 2025-12-01T12:57:29Z day: '10' department: - _id: HeEd doi: 10.1016/j.ejc.2025.104248 ec_funded: 1 external_id: arxiv: - '2212.11380' isi: - '001599061500002' intvolume: ' 132' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2212.11380 month: '10' oa: 1 oa_version: Preprint project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: European Journal of Combinatorics publication_identifier: issn: - 0195-6698 publication_status: epub_ahead publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Flips in two-dimensional hypertriangulations type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 132 year: '2025' ... --- OA_place: repository OA_type: green _id: '20585' abstract: - lang: eng text: Motivated by applications in medical sciences, we study finite chromatic sets in Euclidean space from a topological perspective. Based on the persistent homology for images, kernels and cokernels, we design provably stable homological quantifiers that describe the geometric micro- and macro-structure of how the color classes mingle. These can be efficiently computed using chromatic variants of Delaunay and alpha complexes, and code that does these computations is provided. acknowledgement: "This project has received funding from the European Research\r\nCouncil (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund\r\n(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),\r\ngrant no. I 02979-N35." article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 - first_name: Ondrej full_name: Draganov, Ondrej id: 2B23F01E-F248-11E8-B48F-1D18A9856A87 last_name: Draganov orcid: 0000-0003-0464-3823 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. Chromatic alpha complexes. Foundations of Data Science. 2025;8:30-62. doi:10.3934/fods.2025003 apa: Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (2025). Chromatic alpha complexes. Foundations of Data Science. American Institute of Mathematical Sciences. https://doi.org/10.3934/fods.2025003 chicago: Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “Chromatic Alpha Complexes.” Foundations of Data Science. American Institute of Mathematical Sciences, 2025. https://doi.org/10.3934/fods.2025003. ieee: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “Chromatic alpha complexes,” Foundations of Data Science, vol. 8. American Institute of Mathematical Sciences, pp. 30–62, 2025. ista: Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2025. Chromatic alpha complexes. Foundations of Data Science. 8, 30–62. mla: Cultrera di Montesano, Sebastiano, et al. “Chromatic Alpha Complexes.” Foundations of Data Science, vol. 8, American Institute of Mathematical Sciences, 2025, pp. 30–62, doi:10.3934/fods.2025003. short: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, Foundations of Data Science 8 (2025) 30–62. corr_author: '1' date_created: 2025-11-02T23:01:33Z date_published: 2025-03-01T00:00:00Z date_updated: 2025-11-04T12:25:47Z day: '01' department: - _id: HeEd doi: 10.3934/fods.2025003 ec_funded: 1 external_id: arxiv: - '2212.03128' intvolume: ' 8' language: - iso: eng month: '03' oa_version: Preprint page: 30-62 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Foundations of Data Science publication_identifier: eissn: - 2639-8001 publication_status: epub_ahead publisher: American Institute of Mathematical Sciences quality_controlled: '1' related_material: record: - id: '15091' relation: earlier_version status: public scopus_import: '1' status: public title: Chromatic alpha complexes type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8 year: '2025' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '20657' 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². ' 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. article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: János full_name: Pach, János id: E62E3130-B088-11EA-B919-BF823C25FEA4 last_name: Pach citation: ama: Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. Discrete & Computational Geometry. 2025. doi:10.1007/s00454-025-00796-5 apa: Edelsbrunner, H., & Pach, J. (2025). Maximum Betti numbers of Čech complexes. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-025-00796-5 chicago: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” Discrete & Computational Geometry. Springer Nature, 2025. https://doi.org/10.1007/s00454-025-00796-5. ieee: H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” Discrete & Computational Geometry. Springer Nature, 2025. ista: Edelsbrunner H, Pach J. 2025. Maximum Betti numbers of Čech complexes. Discrete & Computational Geometry. mla: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” Discrete & Computational Geometry, Springer Nature, 2025, doi:10.1007/s00454-025-00796-5. short: H. Edelsbrunner, J. Pach, Discrete & Computational Geometry (2025). corr_author: '1' date_created: 2025-11-19T09:44:58Z date_published: 2025-11-10T00:00:00Z date_updated: 2025-12-01T15:19:21Z day: '10' ddc: - '510' department: - _id: HeEd doi: 10.1007/s00454-025-00796-5 ec_funded: 1 external_id: arxiv: - '2310.14801' isi: - '001610592600001' has_accepted_license: '1' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1007/s00454-025-00796-5 month: '11' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science publication: Discrete & Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: epub_ahead publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '17146' relation: earlier_version status: public scopus_import: '1' status: public title: Maximum Betti numbers of Čech complexes tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2025' ... --- OA_place: repository _id: '21016' abstract: - lang: eng text: Motivated by applications in chemistry, we give a homlogical definition of tunnels, or more generally cobordisms, connecting disjoint parts of a cell complex. For a filtered complex, this defines a persistence module. We give a method for identifying birth and death times using kernel persistence and a matrix reduction algorithm for pairing birth and death times. acknowledgement: "Y. B. B. and L. F. were funded by the Independent Research Fund Denmark, grant\r\nnumber 1026-00037. T. H. was partially supported by the European Research Council\r\n(ERC) Horizon 2020, grant number 788183." article_number: '2505.17858' article_processing_charge: No arxiv: 1 author: - first_name: Yossi full_name: Bleile, Yossi id: 920a7385-7995-11ef-9bfd-8c434cd8f3c2 last_name: Bleile orcid: 0000-0002-4861-9174 - first_name: Lisbeth full_name: Fajstrup, Lisbeth last_name: Fajstrup - first_name: Teresa full_name: Heiss, Teresa id: 4879BB4E-F248-11E8-B48F-1D18A9856A87 last_name: Heiss orcid: 0000-0002-1780-2689 - first_name: Anne Marie full_name: Svane, Anne Marie last_name: Svane - first_name: Søren Strandskov full_name: Sørensen, Søren Strandskov last_name: Sørensen citation: ama: Bleile Y, Fajstrup L, Heiss T, Svane AM, Sørensen SS. Identifying cobordisms using kernel persistence. arXiv. doi:10.48550/arXiv.2505.17858 apa: Bleile, Y., Fajstrup, L., Heiss, T., Svane, A. M., & Sørensen, S. S. (n.d.). Identifying cobordisms using kernel persistence. arXiv. https://doi.org/10.48550/arXiv.2505.17858 chicago: Bleile, Yossi, Lisbeth Fajstrup, Teresa Heiss, Anne Marie Svane, and Søren Strandskov Sørensen. “Identifying Cobordisms Using Kernel Persistence.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2505.17858. ieee: Y. Bleile, L. Fajstrup, T. Heiss, A. M. Svane, and S. S. Sørensen, “Identifying cobordisms using kernel persistence,” arXiv. . ista: Bleile Y, Fajstrup L, Heiss T, Svane AM, Sørensen SS. Identifying cobordisms using kernel persistence. arXiv, 2505.17858. mla: Bleile, Yossi, et al. “Identifying Cobordisms Using Kernel Persistence.” ArXiv, 2505.17858, doi:10.48550/arXiv.2505.17858. short: Y. Bleile, L. Fajstrup, T. Heiss, A.M. Svane, S.S. Sørensen, ArXiv (n.d.). date_created: 2026-01-20T10:12:21Z date_published: 2025-05-23T00:00:00Z date_updated: 2026-01-21T10:34:57Z day: '23' department: - _id: HeEd doi: 10.48550/arXiv.2505.17858 ec_funded: 1 external_id: arxiv: - '2505.17858' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2505.17858 month: '05' oa: 1 oa_version: Preprint project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended publication: arXiv publication_status: submitted status: public title: Identifying cobordisms using kernel persistence type: preprint user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '17149' abstract: - lang: eng text: The approximation of a circle with the edges of a fine square grid distorts the perimeter by a factor about 4/Pi. We prove that this factor is the same on average (in the ergodic sense) for approximations of any rectifiable curve by the edges of any non-exotic Delaunay mosaic (known as Voronoi path), and extend the results to all dimensions, generalizing Voronoi paths to Voronoi scapes. acknowledgement: "The authors thank Ranita Biswas and Tatiana Ezubova for the collaboration on computational experiments that motivated the work reported in this paper. The authors also thank Daniel Bonnema for proofreading and noticing an issue with the original proof of Lemma 4.3.\r\nOpen access funding provided by Institute of Science and Technology (IST Austria).\r\nThis 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." article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Anton full_name: Nikitenko, Anton id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87 last_name: Nikitenko orcid: 0000-0002-0659-3201 citation: ama: Edelsbrunner H, Nikitenko A. Average and expected distortion of Voronoi paths and scapes. Discrete & Computational Geometry. 2025;73:490-499. doi:10.1007/s00454-024-00660-y apa: Edelsbrunner, H., & Nikitenko, A. (2025). Average and expected distortion of Voronoi paths and scapes. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-024-00660-y chicago: Edelsbrunner, Herbert, and Anton Nikitenko. “Average and Expected Distortion of Voronoi Paths and Scapes.” Discrete & Computational Geometry. Springer Nature, 2025. https://doi.org/10.1007/s00454-024-00660-y. ieee: H. Edelsbrunner and A. Nikitenko, “Average and expected distortion of Voronoi paths and scapes,” Discrete & Computational Geometry, vol. 73. Springer Nature, pp. 490–499, 2025. ista: Edelsbrunner H, Nikitenko A. 2025. Average and expected distortion of Voronoi paths and scapes. Discrete & Computational Geometry. 73, 490–499. mla: Edelsbrunner, Herbert, and Anton Nikitenko. “Average and Expected Distortion of Voronoi Paths and Scapes.” Discrete & Computational Geometry, vol. 73, Springer Nature, 2025, pp. 490–99, doi:10.1007/s00454-024-00660-y. short: H. Edelsbrunner, A. Nikitenko, Discrete & Computational Geometry 73 (2025) 490–499. corr_author: '1' date_created: 2024-06-16T22:01:07Z date_published: 2025-03-01T00:00:00Z date_updated: 2026-02-16T12:18:50Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.1007/s00454-024-00660-y ec_funded: 1 external_id: arxiv: - '2012.03350' isi: - '001238566200004' pmid: - '39974750' file: - access_level: open_access checksum: ffb0c818222138f9f113f4bbea41e834 content_type: application/pdf creator: dernst date_created: 2025-04-23T07:31:32Z date_updated: 2025-04-23T07:31:32Z file_id: '19610' file_name: 2025_DiscreteComputGeom_EdelsbrunnerHe.pdf file_size: 283443 relation: main_file success: 1 file_date_updated: 2025-04-23T07:31:32Z has_accepted_license: '1' intvolume: ' 73' isi: 1 language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: 490-499 pmid: 1 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Discrete & Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Average and expected distortion of Voronoi paths and scapes tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 73 year: '2025' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '20260' abstract: - lang: eng text: The medial axis of a set consists of the points in the ambient space without a unique closest point in the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a skeleton topologically equivalent to the original set. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities, various prunings of the medial axis have been proposed in the computational geometry community. Here, we examine one type of pruning, called burning. Because of the good experimental results it was hoped that the burning method of simplifying the medial axis would be stable. In this work, we show a simple example that dashes such hopes. Based on Bing’s house with two rooms, we demonstrate an isotopy of a shape where the medial axis goes from collapsible to non-collapsible. More precisely, we consider the standard deformation retract from the closed ball to Bing’s house with two rooms, but stop just short of the point where Bing’s house becomes two dimensional. This way we obtain an isotopy from the 3-ball to a thickened version of Bing’s house. Under this isotopy, the medial axis goes from collapsible to non-collapsible. We stress that this isotopy can be made generic, in the sense of singularity theory, as developed by Arnol’d and Thom. acknowledgement: "We thank André Lieutier, David Letscher, Ellen Gasparovic, Kathryn Leonard, and Tao Ju for early discussions on this work. We also thank Lu Liu, Yajie Yan, and Tao Ju for sharing code to generate the examples. We further thank Abigail Thompson for discussion on the conjecture and James Damon for sharing his insight in singularity theory. We thank the reviewers for their detailed reviews, which helped to improve the exposition.\r\nOpen access funding provided by Institute of Science and Technology (IST Austria). Partially supported by the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’ and the European Research Council (ERC), grant no. 788183, ‘Alpha Shape Theory Extended’. The first author was supported in part by the National Science Foundation through grants DBI-1759807, CCF-1907612, and CCF-2444309. The fourth author was 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, ANR grant StratMesh, ANR-24-CE48-1899, and the welcome package from IDEX of the Université Côte d’Azur, ANR-15-IDEX-01." article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Erin Wolf full_name: Chambers, Erin Wolf last_name: Chambers - first_name: Christopher D full_name: Fillmore, Christopher D id: 35638A5C-AAC7-11E9-B0BF-5503E6697425 last_name: Fillmore - first_name: Elizabeth R full_name: Stephenson, Elizabeth R id: 2D04F932-F248-11E8-B48F-1D18A9856A87 last_name: Stephenson orcid: 0000-0002-6862-208X - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. Burning or collapsing the medial axis is unstable. La Matematica. 2025;4:811-828. doi:10.1007/s44007-025-00170-0 apa: Chambers, E. W., Fillmore, C. D., Stephenson, E. R., & Wintraecken, M. (2025). Burning or collapsing the medial axis is unstable. La Matematica. Springer Nature. https://doi.org/10.1007/s44007-025-00170-0 chicago: Chambers, Erin Wolf, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs Wintraecken. “Burning or Collapsing the Medial Axis Is Unstable.” La Matematica. Springer Nature, 2025. https://doi.org/10.1007/s44007-025-00170-0. ieee: E. W. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “Burning or collapsing the medial axis is unstable,” La Matematica, vol. 4. Springer Nature, pp. 811–828, 2025. ista: Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. 2025. Burning or collapsing the medial axis is unstable. La Matematica. 4, 811–828. mla: Chambers, Erin Wolf, et al. “Burning or Collapsing the Medial Axis Is Unstable.” La Matematica, vol. 4, Springer Nature, 2025, pp. 811–28, doi:10.1007/s44007-025-00170-0. short: E.W. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, La Matematica 4 (2025) 811–828. corr_author: '1' date_created: 2025-08-31T22:01:33Z date_published: 2025-12-01T00:00:00Z date_updated: 2026-04-07T11:42:48Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.1007/s44007-025-00170-0 ec_funded: 1 file: - access_level: open_access checksum: e2043259194bfcdf3d74c4da8a5a853f content_type: application/pdf creator: dernst date_created: 2025-12-30T07:52:58Z date_updated: 2025-12-30T07:52:58Z file_id: '20885' file_name: 2025_LaMatematica_Chambers.pdf file_size: 2678640 relation: main_file success: 1 file_date_updated: 2025-12-30T07:52:58Z has_accepted_license: '1' intvolume: ' 4' language: - iso: eng month: '12' oa: 1 oa_version: Published Version page: 811-828 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: fc390959-9c52-11eb-aca3-afa58bd282b2 grant_number: M03073 name: Learning and triangulating manifolds via collapses publication: La Matematica publication_identifier: eissn: - 2730-9657 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '21021' relation: dissertation_contains status: public scopus_import: '1' status: public title: Burning or collapsing the medial axis is unstable tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 4 year: '2025' ... --- OA_place: publisher _id: '19630' abstract: - lang: eng text: "This thesis consists of three chapters, each corresponding to one publication. While each of these projects tackles a topic in a different area of research, they all share a common thread in the type of topological structure they handle - a partition of space into volumes separated by interfaces that meet in non-manifold junctions.\r\n\r\nIn Chapter 2, we study clusters of soap bubbles from a simulation perspective. In particular, we develop a surface-only algorithm that couples large scale motion and shape deformation of soap bubble clusters with the small scale evolution of the thin film's thickness, which is responsible for visual phenomena like surface vortices, Newton's interference patterns, capillary waves, and deformation-dependent rupturing of films in a foam. We model film thickness as a reduced degree of freedom in the Navier-Stokes equations and from them derive three sets of equations governing normal and tangential motion of the soap film surface, as well as the evolution of the thin film thickness. We discretize these equations on a non-manifold triangle mesh, extending and adapting operators to handle complex topology. We also present an incompressible fluid solver for 2.5D films and an advection algorithm for convecting fields across non-manifold surface junctions. Our simulations enhance bubble solvers with additional effects caused by convection, rippling, draining, and evaporation of the thin film.\r\n\r\nIn Chapter 3, we introduce a multi-material non-manifold mesh-based surface tracking algorithm that converts mesh defects, such as overlaps, self-intersections, and inversions into topological changes. Our algorithm generalizes prior work on manifold surface tracking with topological changes: it preserves surface features like mesh-based methods, and it robustly handles topological changes like level set methods. Our method also offers improved efficiency and robustness over the state of the art. We demonstrate the effectiveness of the approach on a range of examples, including complex soap film simulations, such as those presented in Chapter 2, but with an order of magnitude more interacting bubbles than what we could achieve before, and Boolean unions of non-manifold meshes consisting of millions of triangles.\r\n\r\nLastly, in Chapter 4, we utilize developments in the theory of random geometric complexes facilitated by observations from Discrete Morse theory. We survey the methods and results obtained with this new approach, and discuss some of its shortcomings. We use simulations to illustrate the results and to form conjectures, getting numerical estimates for combinatorial, topological, and geometric properties of weighted and unweighted Delaunay mosaics, their dual Voronoi tessellations, and the Alpha and Wrap complexes contained in the mosaics." acknowledged_ssus: - _id: ScienComp acknowledgement: The project in Chapter 2 has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No. 638176. The project in Chapter 3 was funded in part by the European Union (ERC-2021-COG 101045083 CoDiNA). The project in Chapter 4 has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreements No 78818 Alpha and No 638176). It was also partially supported by the DFG Collaborative Research Center TRR 109, 'Discretization in Geometry and Dynamics', through grant no. I02979-N35 of the Austrian Science Fund (FWF). Thank you for providing funds to support my work. alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Peter full_name: Synak, Peter id: 331776E2-F248-11E8-B48F-1D18A9856A87 last_name: Synak citation: ama: Synak P. Methods for fluid simulation, surface tracking, and statistics of non-manifold structures. 2025. doi:10.15479/AT-ISTA-19630 apa: Synak, P. (2025). Methods for fluid simulation, surface tracking, and statistics of non-manifold structures. Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-19630 chicago: Synak, Peter. “Methods for Fluid Simulation, Surface Tracking, and Statistics of Non-Manifold Structures.” Institute of Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-19630. ieee: P. Synak, “Methods for fluid simulation, surface tracking, and statistics of non-manifold structures,” Institute of Science and Technology Austria, 2025. ista: Synak P. 2025. Methods for fluid simulation, surface tracking, and statistics of non-manifold structures. Institute of Science and Technology Austria. mla: Synak, Peter. Methods for Fluid Simulation, Surface Tracking, and Statistics of Non-Manifold Structures. Institute of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-19630. short: P. Synak, Methods for Fluid Simulation, Surface Tracking, and Statistics of Non-Manifold Structures, Institute of Science and Technology Austria, 2025. corr_author: '1' date_created: 2025-04-29T09:39:34Z date_published: 2025-04-29T00:00:00Z date_updated: 2026-04-16T08:29:34Z day: '29' ddc: - '519' - '006' degree_awarded: PhD department: - _id: ChWo - _id: GradSch doi: 10.15479/AT-ISTA-19630 ec_funded: 1 file: - access_level: closed checksum: f00b519c27529daa0c3b2d4102b4fa7b content_type: application/x-zip-compressed creator: cchlebak date_created: 2025-04-30T14:02:25Z date_updated: 2025-04-30T14:02:25Z file_id: '19633' file_name: Thesis_source_Heiss_Synak.zip file_size: 60670543 relation: source_file - access_level: open_access checksum: 6e40a2fd3b1b881af1385670854a682e content_type: application/pdf creator: cchlebak date_created: 2025-04-30T14:02:42Z date_updated: 2025-04-30T15:49:16Z file_id: '19634' file_name: Thesis_PDFA_Heiss_Synak.pdf file_size: 21319043 relation: main_file file_date_updated: 2025-04-30T15:49:16Z has_accepted_license: '1' language: - iso: eng month: '04' oa: 1 oa_version: Published Version page: '106' project: - _id: 2533E772-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '638176' name: 'Big Splash: Efficient Simulation of Natural Phenomena at Extremely Large Scales' - _id: 34bc2376-11ca-11ed-8bc3-9a3b3961a088 grant_number: '101045083' name: Computational Discovery of Numerical Algorithms for Animation and Simulation of Natural Phenomena - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 2533E772-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '638176' name: 'Big Splash: Efficient Simulation of Natural Phenomena at Extremely Large Scales' - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '8135' relation: part_of_dissertation status: public - id: '17219' relation: part_of_dissertation status: public - id: '8384' relation: part_of_dissertation status: public status: public supervisor: - first_name: Christopher J full_name: Wojtan, Christopher J id: 3C61F1D2-F248-11E8-B48F-1D18A9856A87 last_name: Wojtan orcid: 0000-0001-6646-5546 title: Methods for fluid simulation, surface tracking, and statistics of non-manifold structures type: dissertation user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd year: '2025' ... --- _id: '14345' abstract: - lang: eng text: For a locally finite set in R2, the order-k Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in k. As an example, a stationary Poisson point process in R2 is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. 6, 85–127 (1970)). acknowledgement: Work by all authors but A. Garber is 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. I 02979-N35. Work by A. Garber is partially supported by the Alexander von Humboldt Foundation. article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Alexey full_name: Garber, Alexey last_name: Garber - first_name: Mohadese full_name: Ghafari, Mohadese last_name: Ghafari - first_name: Teresa full_name: Heiss, Teresa id: 4879BB4E-F248-11E8-B48F-1D18A9856A87 last_name: Heiss orcid: 0000-0002-1780-2689 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry. 2024;72:29-48. doi:10.1007/s00454-023-00566-1 apa: Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., & Saghafian, M. (2024). On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00566-1 chicago: Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafari, Teresa Heiss, and Morteza Saghafian. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” Discrete and Computational Geometry. Springer Nature, 2024. https://doi.org/10.1007/s00454-023-00566-1. ieee: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, and M. Saghafian, “On angles in higher order Brillouin tessellations and related tilings in the plane,” Discrete and Computational Geometry, vol. 72. Springer Nature, pp. 29–48, 2024. ista: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2024. On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry. 72, 29–48. mla: Edelsbrunner, Herbert, et al. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” Discrete and Computational Geometry, vol. 72, Springer Nature, 2024, pp. 29–48, doi:10.1007/s00454-023-00566-1. short: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, Discrete and Computational Geometry 72 (2024) 29–48. corr_author: '1' date_created: 2023-09-17T22:01:10Z date_published: 2024-07-01T00:00:00Z date_updated: 2025-04-23T08:41:59Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.1007/s00454-023-00566-1 ec_funded: 1 external_id: arxiv: - '2204.01076' isi: - '001060727600004' pmid: - '39610762' file: - access_level: open_access checksum: b207b4e00f904e8ea8a30e24f0251f79 content_type: application/pdf creator: dernst date_created: 2024-07-22T09:43:19Z date_updated: 2024-07-22T09:43:19Z file_id: '17301' file_name: 2024_DiscreteComputGeom_Edelsbrunner.pdf file_size: 892019 relation: main_file success: 1 file_date_updated: 2024-07-22T09:43:19Z has_accepted_license: '1' intvolume: ' 72' isi: 1 language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 29-48 pmid: 1 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Discrete and Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: On angles in higher order Brillouin tessellations and related tilings in the plane tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 72 year: '2024' ... --- _id: '18097' 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 \U0001D4AE (either manifold or general set with positive reach) such that one can infer the homotopy of \U0001D4AE 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." 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." alternative_title: - LIPIcs article_number: '87' article_processing_charge: Yes author: - first_name: Dominique full_name: Attali, Dominique last_name: Attali - first_name: Hana full_name: Kourimska, Hana id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E last_name: Kourimska orcid: 0000-0001-7841-0091 - first_name: Christopher D full_name: Fillmore, Christopher D id: 35638A5C-AAC7-11E9-B0BF-5503E6697425 last_name: Fillmore - first_name: Ishika full_name: Ghosh, Ishika id: ee449b28-344d-11ef-a6d5-9ca430e9e9ff last_name: Ghosh - first_name: Andre full_name: Lieutier, Andre last_name: Lieutier - first_name: Elizabeth R full_name: Stephenson, Elizabeth R id: 2D04F932-F248-11E8-B48F-1D18A9856A87 last_name: Stephenson orcid: 0000-0002-6862-208X - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: 'Attali D, Kourimska H, Fillmore CD, et al. The ultimate frontier: An optimality construction for homotopy inference (media exposition). In: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.87' apa: 'Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson, E. R., & Wintraecken, M. (2024). The ultimate frontier: An optimality construction for homotopy inference (media exposition). In 40th International Symposium on Computational Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.87' 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 40th International Symposium on Computational Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.87.' ieee: 'D. Attali et al., “The ultimate frontier: An optimality construction for homotopy inference (media exposition),” in 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293.' 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.' mla: 'Attali, Dominique, et al. “The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition).” 40th International Symposium on Computational Geometry, vol. 293, 87, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.87.' 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. conference: end_date: 2024-06-14 location: Athens, Greece name: 'SoCG: Symposium on Computational Geometry' start_date: 2024-06-11 corr_author: '1' date_created: 2024-09-19T10:29:48Z date_published: 2024-06-06T00:00:00Z date_updated: 2025-04-15T07:16:58Z day: '06' ddc: - '000' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2024.87 ec_funded: 1 file: - access_level: open_access checksum: 9355c2e60b8ec285e1b22719c5b73f1a content_type: application/pdf creator: dernst date_created: 2024-09-19T10:30:37Z date_updated: 2024-09-19T10:30:37Z file_id: '18098' file_name: 2024_LIPICs_Attali.pdf file_size: 3507177 relation: main_file success: 1 file_date_updated: 2024-09-19T10:30:37Z has_accepted_license: '1' intvolume: ' 293' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: fc390959-9c52-11eb-aca3-afa58bd282b2 grant_number: M03073 name: Learning and triangulating manifolds via collapses publication: 40th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959773164' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' status: public title: 'The ultimate frontier: An optimality construction for homotopy inference (media exposition)' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 293 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '18556' abstract: - lang: eng text: Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined length of the minimum spanning trees of B and A⧵B divided by the length of the minimum spanning tree of A. The question of the supremum, over all sets A, of the maximum, over all subsets B, is related to the Steiner ratio, and we prove this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than 1.25. acknowledgement: 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. alternative_title: - LIPIcs article_number: '3' article_processing_charge: Yes arxiv: 1 author: - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 - first_name: Ondrej full_name: Draganov, Ondrej id: 2B23F01E-F248-11E8-B48F-1D18A9856A87 last_name: Draganov orcid: 0000-0003-0464-3823 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. The Euclidean MST-ratio for bi-colored lattices. In: 32nd International Symposium on Graph Drawing and Network Visualization. Vol 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.GD.2024.3' apa: 'Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (2024). The Euclidean MST-ratio for bi-colored lattices. In 32nd International Symposium on Graph Drawing and Network Visualization (Vol. 320). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.3' chicago: Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “The Euclidean MST-Ratio for Bi-Colored Lattices.” In 32nd International Symposium on Graph Drawing and Network Visualization, Vol. 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.GD.2024.3. ieee: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “The Euclidean MST-ratio for bi-colored lattices,” in 32nd International Symposium on Graph Drawing and Network Visualization, Vienna, Austria, 2024, vol. 320. ista: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2024. The Euclidean MST-ratio for bi-colored lattices. 32nd International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LIPIcs, vol. 320, 3.' mla: Cultrera di Montesano, Sebastiano, et al. “The Euclidean MST-Ratio for Bi-Colored Lattices.” 32nd International Symposium on Graph Drawing and Network Visualization, vol. 320, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.GD.2024.3. short: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, in:, 32nd International Symposium on Graph Drawing and Network Visualization, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-09-20 location: Vienna, Austria name: 'GD: Graph Drawing and Network Visualization' start_date: 2024-09-18 corr_author: '1' date_created: 2024-11-17T23:01:47Z date_published: 2024-10-28T00:00:00Z date_updated: 2025-12-02T13:50:50Z day: '28' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPIcs.GD.2024.3 ec_funded: 1 external_id: arxiv: - '2403.10204' isi: - '001540278400001' file: - access_level: open_access checksum: 5f9b35e115c3d375e99be78da9054cb4 content_type: application/pdf creator: dernst date_created: 2024-11-18T07:49:25Z date_updated: 2024-11-18T07:49:25Z file_id: '18560' file_name: 2024_LIPIcs_CultreradiMontesano.pdf file_size: 908541 relation: main_file success: 1 file_date_updated: 2024-11-18T07:49:25Z has_accepted_license: '1' intvolume: ' 320' isi: 1 language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: 32nd International Symposium on Graph Drawing and Network Visualization publication_identifier: isbn: - '9783959773430' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: The Euclidean MST-ratio for bi-colored lattices tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 320 year: '2024' ... --- OA_place: publisher OA_type: hybrid _id: '15380' abstract: - lang: eng text: The depth of a cell in an arrangement of n (non-vertical) great-spheres in Sd is the number of great-spheres that pass above the cell. We prove Euler-type relations, which imply extensions of the classic Dehn–Sommerville relations for convex polytopes to sublevel sets of the depth function, and we use the relations to extend the expressions for the number of faces of neighborly polytopes to the number of cells of levels in neighborly arrangements. acknowledgement: "The authors thank Uli Wagner and Emo Welzl for comments on an earlier version of this paper, and for pointing out related work in the prior literature.\r\nOpen access funding provided by Institute of Science and Technology (IST Austria). 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." article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Ranita full_name: Biswas, Ranita id: 3C2B033E-F248-11E8-B48F-1D18A9856A87 last_name: Biswas orcid: 0000-0002-5372-7890 - first_name: Sebastiano full_name: Cultrera Di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera Di Montesano orcid: 0000-0001-6249-0832 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Depth in arrangements: Dehn–Sommerville–Euler relations with applications. Journal of Applied and Computational Topology. 2024;8:557-578. doi:10.1007/s41468-024-00173-w' apa: 'Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M. (2024). Depth in arrangements: Dehn–Sommerville–Euler relations with applications. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-024-00173-w' chicago: 'Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Depth in Arrangements: Dehn–Sommerville–Euler Relations with Applications.” Journal of Applied and Computational Topology. Springer Nature, 2024. https://doi.org/10.1007/s41468-024-00173-w.' ieee: 'R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Depth in arrangements: Dehn–Sommerville–Euler relations with applications,” Journal of Applied and Computational Topology, vol. 8. Springer Nature, pp. 557–578, 2024.' ista: 'Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2024. Depth in arrangements: Dehn–Sommerville–Euler relations with applications. Journal of Applied and Computational Topology. 8, 557–578.' mla: 'Biswas, Ranita, et al. “Depth in Arrangements: Dehn–Sommerville–Euler Relations with Applications.” Journal of Applied and Computational Topology, vol. 8, Springer Nature, 2024, pp. 557–78, doi:10.1007/s41468-024-00173-w.' short: R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Journal of Applied and Computational Topology 8 (2024) 557–578. corr_author: '1' date_created: 2024-05-12T22:01:03Z date_published: 2024-09-01T00:00:00Z date_updated: 2025-05-14T09:27:57Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.1007/s41468-024-00173-w ec_funded: 1 external_id: pmid: - '39308789' file: - access_level: open_access checksum: 0ee15c1493a6413cf356ab2f32c81a9e content_type: application/pdf creator: dernst date_created: 2025-04-23T08:01:36Z date_updated: 2025-04-23T08:01:36Z file_id: '19612' file_name: 2024_JourApplCompTopo_BiswasRa.pdf file_size: 522831 relation: main_file success: 1 file_date_updated: 2025-04-23T08:01:36Z has_accepted_license: '1' intvolume: ' 8' language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: 557-578 pmid: 1 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Journal of Applied and Computational Topology publication_identifier: eissn: - 2367-1734 issn: - 2367-1726 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '11658' relation: earlier_version status: public scopus_import: '1' status: public title: 'Depth in arrangements: Dehn–Sommerville–Euler relations with applications' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8 year: '2024' ... --- _id: '17144' abstract: - lang: eng text: "We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let \U0001D4AE ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set \U0001D4AE. Consider the space of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant. The map from this space of diffeomorphisms (endowed with a Banach norm) to the space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping a diffeomorphism F to the closure of the medial axis of F(\U0001D4AE), is Lipschitz. This extends a previous stability result of Chazal and Soufflet on the stability of the medial axis of C² manifolds under C² ambient diffeomorphisms." 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. I 02979-N35.\r\nSupported 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ô d'Azur.\r\nWe are greatly indebted to Fred Chazal for sharing his insights. We further thank Erin Chambers, Christopher Fillmore, and Elizabeth Stephenson for early discussions and all members of the Edelsbrunner group (Institute of Science and Technology Austria) and the Datashape team (Inria) for the atmosphere in which this research was conducted." alternative_title: - LIPIcs article_number: '69' article_processing_charge: No arxiv: 1 author: - first_name: Hana full_name: Kourimska, Hana id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E last_name: Kourimska orcid: 0000-0001-7841-0091 - first_name: André full_name: Lieutier, André last_name: Lieutier - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: 'Kourimska H, Lieutier A, Wintraecken M. The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. In: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.69' apa: 'Kourimska, H., Lieutier, A., & Wintraecken, M. (2024). The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. In 40th International Symposium on Computational Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.69' chicago: Kourimska, Hana, André Lieutier, and Mathijs Wintraecken. “The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.” In 40th International Symposium on Computational Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.69. ieee: H. Kourimska, A. Lieutier, and M. Wintraecken, “The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms,” in 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293. ista: 'Kourimska H, Lieutier A, Wintraecken M. 2024. The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 69.' mla: Kourimska, Hana, et al. “The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.” 40th International Symposium on Computational Geometry, vol. 293, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.69. short: H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-06-14 location: Athens, Greece name: 'SoCG: Symposium on Computational Geometry' date_created: 2024-06-16T22:01:06Z date_published: 2024-06-01T00:00:00Z date_updated: 2025-04-15T07:16:58Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2024.69 ec_funded: 1 external_id: arxiv: - '2212.01118' file: - access_level: open_access checksum: b40ff456c19294adb5d9613fcfd751c6 content_type: application/pdf creator: dernst date_created: 2024-06-17T08:33:40Z date_updated: 2024-06-17T08:33:40Z file_id: '17150' file_name: 2024_LIPICS_Kourimska.pdf file_size: 1612558 relation: main_file success: 1 file_date_updated: 2024-06-17T08:33:40Z has_accepted_license: '1' intvolume: ' 293' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: fc390959-9c52-11eb-aca3-afa58bd282b2 grant_number: M03073 name: Learning and triangulating manifolds via collapses publication: 40th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959773164' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 293 year: '2024' ... --- _id: '17146' 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. 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." alternative_title: - LIPIcs article_number: '53' article_processing_charge: No arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: János full_name: Pach, János id: E62E3130-B088-11EA-B919-BF823C25FEA4 last_name: Pach citation: ama: 'Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.53' apa: 'Edelsbrunner, H., & Pach, J. (2024). Maximum Betti numbers of Čech complexes. In 40th International Symposium on Computational Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.53' chicago: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” In 40th International Symposium on Computational Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.53. ieee: H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293. 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.' mla: Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” 40th International Symposium on Computational Geometry, vol. 293, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.53. short: H. Edelsbrunner, J. Pach, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-06-14 location: Athens, Greece name: 'SoCG: Symposium on Computational Geometry' start_date: 2024-06-11 date_created: 2024-06-16T22:01:06Z date_published: 2024-06-01T00:00:00Z date_updated: 2025-12-01T15:19:20Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2024.53 ec_funded: 1 external_id: arxiv: - '2310.14801' file: - access_level: open_access checksum: 5442d44fb89d77477a87668d6e61aac9 content_type: application/pdf creator: dernst date_created: 2024-06-17T08:46:33Z date_updated: 2024-06-17T08:46:33Z file_id: '17152' file_name: 2024_LIPICS_Edelsbrunner.pdf file_size: 766562 relation: main_file success: 1 file_date_updated: 2024-06-17T08:46:33Z has_accepted_license: '1' intvolume: ' 293' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science publication: 40th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959773164' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '20657' relation: later_version status: public scopus_import: '1' status: public title: Maximum Betti numbers of Čech complexes tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 293 year: '2024' ... --- _id: '17170' abstract: - lang: eng text: "In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds with positive reach embedded in ℝ^d. We extend their results in the following ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with lower bounded sectional curvature. - In both types of ambient spaces, we study sets of positive reach - a significantly more general setting than C² manifolds - as well as general manifolds of positive reach. - The sample P of a set (or a manifold) \U0001D4AE of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and \U0001D4AE. We provide tight bounds in terms of ε and δ, that guarantee that there exists a parameter r such that the union of balls of radius r centred at the sample P deformation-retracts to \U0001D4AE. We exhibit their tightness by an explicit construction. We carefully distinguish the roles of δ and ε. This is not only essential to achieve tight bounds, but also sensible in practical situations, since it allows one to adapt the bound according to sample density and the amount of noise present in the sample separately." 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. I 02979-N35.\r\nWintraecken, Mathijs: 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." alternative_title: - LIPIcs article_processing_charge: No arxiv: 1 author: - first_name: Dominique full_name: Attali, Dominique last_name: Attali - first_name: Hana full_name: Kourimska, Hana id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E last_name: Kourimska orcid: 0000-0001-7841-0091 - first_name: Christopher D full_name: Fillmore, Christopher D id: 35638A5C-AAC7-11E9-B0BF-5503E6697425 last_name: Fillmore - first_name: Ishika full_name: Ghosh, Ishika id: ee449b28-344d-11ef-a6d5-9ca430e9e9ff last_name: Ghosh - first_name: André full_name: Lieutier, André last_name: Lieutier - first_name: Elizabeth R full_name: Stephenson, Elizabeth R id: 2D04F932-F248-11E8-B48F-1D18A9856A87 last_name: Stephenson orcid: 0000-0002-6862-208X - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: 'Attali D, Kourimska H, Fillmore CD, et al. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds. In: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:11:1-11:19. doi:10.4230/LIPIcs.SoCG.2024.11' apa: 'Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson, E. R., & Wintraecken, M. (2024). Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds. In 40th International Symposium on Computational Geometry (Vol. 293, p. 11:1-11:19). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.11' chicago: Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh, André Lieutier, Elizabeth R Stephenson, and Mathijs Wintraecken. “Tight Bounds for the Learning of Homotopy à La Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds.” In 40th International Symposium on Computational Geometry, 293:11:1-11:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.11. ieee: D. Attali et al., “Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds,” in 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293, p. 11:1-11:19. ista: 'Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken M. 2024. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 11:1-11:19.' mla: Attali, Dominique, et al. “Tight Bounds for the Learning of Homotopy à La Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds.” 40th International Symposium on Computational Geometry, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19, doi:10.4230/LIPIcs.SoCG.2024.11. 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, p. 11:1-11:19. conference: end_date: 2024-06-14 location: Athens, Greece name: 'SoCG: Symposium on Computational Geometry' start_date: 2024-06-11 date_created: 2024-06-25T11:45:58Z date_published: 2024-06-06T00:00:00Z date_updated: 2025-04-15T07:16:57Z day: '06' ddc: - '516' department: - _id: GradSch - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2024.11 ec_funded: 1 external_id: arxiv: - '2206.10485' file: - access_level: open_access checksum: 6a2ddc8b51aa58f197a8b294750f1f8d content_type: application/pdf creator: cfillmor date_created: 2024-06-25T11:47:26Z date_updated: 2024-06-25T11:47:26Z file_id: '17171' file_name: LIPIcs.SoCG.2024.11.pdf file_size: 20886142 relation: main_file success: 1 file_date_updated: 2024-06-25T11:47:26Z has_accepted_license: '1' intvolume: ' 293' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 11:1-11:19 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: fc390959-9c52-11eb-aca3-afa58bd282b2 grant_number: M03073 name: Learning and triangulating manifolds via collapses publication: 40th International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959773164' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 293 year: '2024' ...