[{"citation":{"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.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">10.4230/LIPIcs.SoCG.2024.69</a>.","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 <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">https://doi.org/10.4230/LIPIcs.SoCG.2024.69</a>.","apa":"Kourimska, H., Lieutier, A., &#38; Wintraecken, M. (2024). The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">https://doi.org/10.4230/LIPIcs.SoCG.2024.69</a>","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.","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 <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","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: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">10.4230/LIPIcs.SoCG.2024.69</a>","short":"H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"arxiv":1,"has_accepted_license":"1","title":"The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under 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.","oa_version":"Published Version","scopus_import":"1","article_processing_charge":"No","_id":"17144","oa":1,"language":[{"iso":"eng"}],"author":[{"orcid":"0000-0001-7841-0091","full_name":"Kourimska, Hana","last_name":"Kourimska","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","first_name":"Hana"},{"first_name":"André","full_name":"Lieutier, André","last_name":"Lieutier"},{"first_name":"Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs"}],"license":"https://creativecommons.org/licenses/by/4.0/","type":"conference","day":"01","status":"public","month":"06","quality_controlled":"1","article_number":"69","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773164"]},"file_date_updated":"2024-06-17T08:33:40Z","publication":"40th International Symposium on Computational Geometry","intvolume":"       293","file":[{"date_updated":"2024-06-17T08:33:40Z","file_size":1612558,"file_name":"2024_LIPICS_Kourimska.pdf","access_level":"open_access","creator":"dernst","success":1,"content_type":"application/pdf","date_created":"2024-06-17T08:33:40Z","relation":"main_file","checksum":"b40ff456c19294adb5d9613fcfd751c6","file_id":"17150"}],"publication_status":"published","external_id":{"arxiv":["2212.01118"]},"department":[{"_id":"HeEd"}],"ec_funded":1,"abstract":[{"text":"We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let 𝒮 ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set 𝒮. 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(𝒮), 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.","lang":"eng"}],"alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.SoCG.2024.69","ddc":["510"],"project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","call_identifier":"H2020","name":"Alpha Shape Theory Extended"},{"name":"Mathematics, Computer Science","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","call_identifier":"FWF"},{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Persistence and stability of geometric complexes"},{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"date_published":"2024-06-01T00:00:00Z","volume":293,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"date_updated":"2025-04-15T07:16:58Z","conference":{"end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry","location":"Athens, Greece"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2024","date_created":"2024-06-16T22:01:06Z"},{"ddc":["510"],"date_published":"2024-06-01T00:00:00Z","conference":{"start_date":"2024-06-11","location":"Athens, Greece","end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry"},"volume":293,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"date_updated":"2024-06-17T08:41:56Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2024-06-16T22:01:06Z","year":"2024","file_date_updated":"2024-06-17T08:40:04Z","intvolume":"       293","file":[{"date_created":"2024-06-17T08:40:04Z","success":1,"content_type":"application/pdf","file_id":"17151","checksum":"fbad1de06383a6b7e8a1cb3e8c7205ce","relation":"main_file","access_level":"open_access","file_size":1430896,"file_name":"2024_LIPICS_Rote.pdf","date_updated":"2024-06-17T08:40:04Z","creator":"dernst"}],"publication":"40th International Symposium on Computational Geometry","external_id":{"arxiv":["2402.15787"]},"department":[{"_id":"HeEd"}],"publication_status":"published","alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.SoCG.2024.76","abstract":[{"lang":"eng","text":"Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes."}],"_id":"17145","article_processing_charge":"No","author":[{"first_name":"Günter","last_name":"Rote","full_name":"Rote, Günter"},{"full_name":"Rüber, Moritz","last_name":"Rüber","first_name":"Moritz"},{"last_name":"Saghafian","full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824","first_name":"Morteza"}],"oa":1,"language":[{"iso":"eng"}],"status":"public","type":"conference","day":"01","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_number":"76","publication_identifier":{"isbn":["9783959773164"],"issn":["1868-8969"]},"quality_controlled":"1","month":"06","has_accepted_license":"1","citation":{"apa":"Rote, G., Rüber, M., &#38; Saghafian, M. (2024). Grid peeling of parabolas. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">https://doi.org/10.4230/LIPIcs.SoCG.2024.76</a>","ista":"Rote G, Rüber M, Saghafian M. 2024. Grid peeling of parabolas. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 76.","ama":"Rote G, Rüber M, Saghafian M. Grid peeling of parabolas. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">10.4230/LIPIcs.SoCG.2024.76</a>","short":"G. Rote, M. Rüber, M. Saghafian, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ieee":"G. Rote, M. Rüber, and M. Saghafian, “Grid peeling of parabolas,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","mla":"Rote, Günter, et al. “Grid Peeling of Parabolas.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 76, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">10.4230/LIPIcs.SoCG.2024.76</a>.","chicago":"Rote, Günter, Moritz Rüber, and Morteza Saghafian. “Grid Peeling of Parabolas.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">https://doi.org/10.4230/LIPIcs.SoCG.2024.76</a>."},"arxiv":1,"title":"Grid peeling of parabolas","acknowledgement":"Part of this work was done while G.R. enjoyed the hospitality of the Institute of Science and Technology Austria (ISTA) as a visiting professor during his sabbatical in the winter semester 2022/23.","scopus_import":"1","oa_version":"Published Version"},{"quality_controlled":"1","month":"06","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773164"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"06","type":"conference","status":"public","page":"11:1-11:19","language":[{"iso":"eng"}],"oa":1,"author":[{"first_name":"Dominique","last_name":"Attali","full_name":"Attali, Dominique"},{"first_name":"Hana","last_name":"Kourimska","full_name":"Kourimska, Hana","orcid":"0000-0001-7841-0091","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E"},{"id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","last_name":"Fillmore","full_name":"Fillmore, Christopher D","first_name":"Christopher D"},{"first_name":"Ishika","id":"ee449b28-344d-11ef-a6d5-9ca430e9e9ff","full_name":"Ghosh, Ishika","last_name":"Ghosh"},{"last_name":"Lieutier","full_name":"Lieutier, André","first_name":"André"},{"first_name":"Elizabeth R","full_name":"Stephenson, Elizabeth R","orcid":"0000-0002-6862-208X","last_name":"Stephenson","id":"2D04F932-F248-11E8-B48F-1D18A9856A87"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs"}],"article_processing_charge":"No","_id":"17170","oa_version":"Published Version","scopus_import":"1","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.","title":"Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds","arxiv":1,"citation":{"apa":"Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson, E. R., &#38; 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 <i>40th International Symposium on Computational Geometry</i> (Vol. 293, p. 11:1-11:19). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">https://doi.org/10.4230/LIPIcs.SoCG.2024.11</a>","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.","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.","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: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:11:1-11:19. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">10.4230/LIPIcs.SoCG.2024.11</a>","ieee":"D. Attali <i>et al.</i>, “Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293, p. 11:1-11:19.","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 <i>40th International Symposium on Computational Geometry</i>, 293:11:1-11:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">https://doi.org/10.4230/LIPIcs.SoCG.2024.11</a>.","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.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">10.4230/LIPIcs.SoCG.2024.11</a>."},"has_accepted_license":"1","year":"2024","date_created":"2024-06-25T11:45:58Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-04-15T07:16:57Z","volume":293,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"conference":{"location":"Athens, Greece","start_date":"2024-06-11","end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry"},"date_published":"2024-06-06T00:00:00Z","ddc":["516"],"project":[{"call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","name":"Alpha Shape Theory Extended"},{"grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Mathematics, Computer Science"},{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"},{"call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","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"}],"ec_funded":1,"abstract":[{"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) 𝒮 of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and 𝒮. 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 𝒮. 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.","lang":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2024.11","alternative_title":["LIPIcs"],"publication_status":"published","department":[{"_id":"GradSch"},{"_id":"HeEd"}],"external_id":{"arxiv":["2206.10485"]},"publication":"40th International Symposium on Computational Geometry","intvolume":"       293","file":[{"creator":"cfillmor","access_level":"open_access","date_updated":"2024-06-25T11:47:26Z","file_size":20886142,"file_name":"LIPIcs.SoCG.2024.11.pdf","file_id":"17171","checksum":"6a2ddc8b51aa58f197a8b294750f1f8d","relation":"main_file","date_created":"2024-06-25T11:47:26Z","content_type":"application/pdf","success":1}],"file_date_updated":"2024-06-25T11:47:26Z"},{"quality_controlled":"1","month":"06","article_number":"87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"isbn":["9783959773164"]},"type":"conference","day":"06","status":"public","oa":1,"language":[{"iso":"eng"}],"author":[{"first_name":"Dominique","last_name":"Attali","full_name":"Attali, Dominique"},{"first_name":"Hana","last_name":"Kourimska","full_name":"Kourimska, Hana","orcid":"0000-0001-7841-0091","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E"},{"id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","last_name":"Fillmore","full_name":"Fillmore, Christopher D","first_name":"Christopher D"},{"last_name":"Ghosh","full_name":"Ghosh, Ishika","id":"ee449b28-344d-11ef-a6d5-9ca430e9e9ff","first_name":"Ishika"},{"first_name":"Andre","last_name":"Lieutier","full_name":"Lieutier, Andre"},{"full_name":"Stephenson, Elizabeth R","orcid":"0000-0002-6862-208X","last_name":"Stephenson","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","first_name":"Elizabeth R"},{"orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs"}],"article_processing_charge":"Yes","corr_author":"1","_id":"18097","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.","oa_version":"Published Version","title":"The ultimate frontier: An optimality construction for homotopy inference (media exposition)","citation":{"chicago":"Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh, Andre Lieutier, Elizabeth R Stephenson, and Mathijs Wintraecken. “The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition).” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">https://doi.org/10.4230/LIPIcs.SoCG.2024.87</a>.","mla":"Attali, Dominique, et al. “The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition).” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 87, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">10.4230/LIPIcs.SoCG.2024.87</a>.","short":"D. Attali, H. Kourimska, C.D. Fillmore, I. Ghosh, A. Lieutier, E.R. Stephenson, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ama":"Attali D, Kourimska H, Fillmore CD, et al. The ultimate frontier: An optimality construction for homotopy inference (media exposition). In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">10.4230/LIPIcs.SoCG.2024.87</a>","ieee":"D. Attali <i>et al.</i>, “The ultimate frontier: An optimality construction for homotopy inference (media exposition),” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","ista":"Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken M. 2024. The ultimate frontier: An optimality construction for homotopy inference (media exposition). 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 87.","apa":"Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson, E. R., &#38; Wintraecken, M. (2024). The ultimate frontier: An optimality construction for homotopy inference (media exposition). In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.87\">https://doi.org/10.4230/LIPIcs.SoCG.2024.87</a>"},"has_accepted_license":"1","year":"2024","date_created":"2024-09-19T10:29:48Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":293,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"date_updated":"2025-04-15T07:16:58Z","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14","location":"Athens, Greece","start_date":"2024-06-11"},"project":[{"name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","call_identifier":"H2020"},{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","name":"Mathematics, Computer Science"},{"name":"Persistence and stability of geometric complexes","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"ddc":["000"],"date_published":"2024-06-06T00:00:00Z","abstract":[{"text":"In our companion paper \"Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds\" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.","lang":"eng"}],"ec_funded":1,"alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.SoCG.2024.87","publication_status":"published","department":[{"_id":"HeEd"}],"file":[{"date_created":"2024-09-19T10:30:37Z","success":1,"content_type":"application/pdf","file_id":"18098","checksum":"9355c2e60b8ec285e1b22719c5b73f1a","relation":"main_file","access_level":"open_access","date_updated":"2024-09-19T10:30:37Z","file_size":3507177,"file_name":"2024_LIPICs_Attali.pdf","creator":"dernst"}],"publication":"40th International Symposium on Computational Geometry","intvolume":"       293","file_date_updated":"2024-09-19T10:30:37Z"},{"_id":"18917","corr_author":"1","article_processing_charge":"Yes","author":[{"full_name":"Aronov, Boris","last_name":"Aronov","first_name":"Boris"},{"full_name":"Basit, Abdul","last_name":"Basit","first_name":"Abdul"},{"full_name":"Ramesh, Indu","last_name":"Ramesh","first_name":"Indu"},{"first_name":"Gianluca","last_name":"Tasinato","full_name":"Tasinato, Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"language":[{"iso":"eng"}],"oa":1,"OA_place":"publisher","status":"public","page":"8:1-8:15","day":"06","type":"conference","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"isbn":["9783959773164"]},"quality_controlled":"1","month":"06","has_accepted_license":"1","arxiv":1,"citation":{"mla":"Aronov, Boris, et al. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>.","chicago":"Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. “Eight-Partitioning Points in 3D, and Efficiently Too.” In <i>40th International Symposium on Computational Geometry</i>, 293:8:1-8:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>.","apa":"Aronov, B., Basit, A., Ramesh, I., Tasinato, G., &#38; Wagner, U. (2024). Eight-partitioning points in 3D, and efficiently too. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293, p. 8:1-8:15). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>","ista":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2024. Eight-partitioning points in 3D, and efficiently too. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 293, 8:1-8:15.","ama":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. Eight-partitioning points in 3D, and efficiently too. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:8:1-8:15. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>","short":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15.","ieee":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning points in 3D, and efficiently too,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293, p. 8:1-8:15."},"title":"Eight-partitioning points in 3D, and efficiently too","related_material":{"record":[{"status":"public","relation":"later_version","id":"19860"}]},"OA_type":"gold","acknowledgement":"Aronov, Boris: Work has been supported by NSF grants CCF 15-40656 and CCF 20-08551, and by grant 2014/170 from the US-Israel Binational Science Foundation. Part of this research was conducted while BA was visiting ISTA in the summers of 2022 and 2023. The visit of BA to ISTA in the summer of 2022 was supported by an ISTA Visiting Professorship.\r\nBasit, Abdul: Work has been supported by Australian Research Council grant DP220102212.\r\nRamesh, Indu: Work supported by a Tandon School of Engineering Fellowship and by NSF Grant CCF-20-08551.\r\nBA and AB would like to thank William Steiger for insightful initial discussions of the problems addressed in this work.","oa_version":"Published Version","scopus_import":"1","date_published":"2024-06-06T00:00:00Z","ddc":["510"],"conference":{"start_date":"2024-06-11","location":"Athens, Greece","name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14"},"date_updated":"2026-07-23T11:14:45Z","volume":293,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2025-01-27T14:19:17Z","year":"2024","file_date_updated":"2025-01-27T14:17:37Z","intvolume":"       293","publication":"40th International Symposium on Computational Geometry","file":[{"file_name":"2024_LIPICs_Aronov.pdf","file_size":880725,"date_updated":"2025-01-27T14:17:37Z","access_level":"open_access","creator":"dernst","success":1,"content_type":"application/pdf","date_created":"2025-01-27T14:17:37Z","relation":"main_file","file_id":"18918","checksum":"443aa29ea5d948e917cfccd681dcf176"}],"department":[{"_id":"UlWa"},{"_id":"GradSch"}],"external_id":{"arxiv":["2403.02627"]},"publication_status":"published","doi":"10.4230/LIPIcs.SoCG.2024.8","abstract":[{"text":"An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument.\r\nWe prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction.\r\nMoreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).","lang":"eng"}]},{"date_published":"2024-06-01T00:00:00Z","project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"name":"Persistence and stability of geometric complexes","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"},{"name":"Mathematics, Computer Science","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","call_identifier":"FWF"}],"ddc":["510"],"conference":{"end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2024-06-11","location":"Athens, Greece"},"date_updated":"2026-07-27T08:15:58Z","volume":293,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2024-06-16T22:01:06Z","year":"2024","file_date_updated":"2024-06-17T08:46:33Z","intvolume":"       293","publication":"40th International Symposium on Computational Geometry","file":[{"content_type":"application/pdf","success":1,"date_created":"2024-06-17T08:46:33Z","relation":"main_file","checksum":"5442d44fb89d77477a87668d6e61aac9","file_id":"17152","date_updated":"2024-06-17T08:46:33Z","file_name":"2024_LIPICS_Edelsbrunner.pdf","file_size":766562,"access_level":"open_access","creator":"dernst"}],"department":[{"_id":"HeEd"}],"external_id":{"arxiv":["2310.14801"]},"publication_status":"published","doi":"10.4230/LIPIcs.SoCG.2024.53","alternative_title":["LIPIcs"],"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."}],"ec_funded":1,"_id":"17146","article_processing_charge":"No","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"id":"E62E3130-B088-11EA-B919-BF823C25FEA4","last_name":"Pach","full_name":"Pach, János","first_name":"János"}],"oa":1,"language":[{"iso":"eng"}],"status":"public","day":"01","type":"conference","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"isbn":["9783959773164"],"issn":["1868-8969"]},"article_number":"53","quality_controlled":"1","month":"06","has_accepted_license":"1","arxiv":1,"citation":{"chicago":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>.","mla":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>.","ista":"Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 53.","apa":"Edelsbrunner, H., &#38; Pach, J. (2024). Maximum Betti numbers of Čech complexes. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>","ieee":"H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","ama":"Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>","short":"H. Edelsbrunner, J. Pach, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"title":"Maximum Betti numbers of Čech complexes","related_material":{"record":[{"status":"public","relation":"later_version","id":"20657"}]},"oa_version":"Published Version","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.","scopus_import":"1"}]