[{"type":"book_chapter","acknowledgement":"We thank the reviewers for both SODA and ATMCS for their comments, whichimproved the exposition. We thank Kate Turner for discussion and Clément Maria for pointing out thatAlexander’s theorem was already (well) known. Mathijs Wintraecken would like to express his gratitude tothe administrative support he received from University of Notre Dame during his visit and from Sophie Honnoratand Stephanie Verdonck at Inria in general.This work has been supported by the ANR grant StratMesh, ANR-24-CE48-1899, by NSF award 2444309, andthe welcome package from IDEX of the Université Côte d’Azur, ANR-15-IDEX-01.","status":"public","publication_identifier":{"eisbn":["9781611978971"]},"place":"Philadelphia, PA, United States","OA_place":"repository","doi":"10.1137/1.9781611978971.225","related_material":{"record":[{"id":"21051","status":"public","relation":"earlier_version"}]},"page":"6240-6263","language":[{"iso":"eng"}],"year":"2026","oa":1,"arxiv":1,"month":"01","editor":[{"last_name":"Green Larsen","first_name":"Kasper","full_name":"Green Larsen, Kasper"},{"full_name":"Saha, Barna","first_name":"Barna","last_name":"Saha"}],"_id":"21056","oa_version":"Preprint","article_processing_charge":"No","day":"07","department":[{"_id":"HeEd"}],"publisher":"Society for Industrial and Applied Mathematics","citation":{"apa":"Chambers, E. W., Fillmore, C. D., Stephenson, E. R., &#38; Wintraecken, M. (2026). Braiding Vineyards. In K. Green Larsen &#38; B. Saha (Eds.), <i>Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 6240–6263). Philadelphia, PA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611978971.225\">https://doi.org/10.1137/1.9781611978971.225</a>","ama":"Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. Braiding Vineyards. In: Green Larsen K, Saha B, eds. <i>Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Philadelphia, PA, United States: Society for Industrial and Applied Mathematics; 2026:6240-6263. doi:<a href=\"https://doi.org/10.1137/1.9781611978971.225\">10.1137/1.9781611978971.225</a>","chicago":"Chambers, Erin W., Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs Wintraecken. “Braiding Vineyards.” In <i>Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, edited by Kasper Green Larsen and Barna Saha, 6240–63. Philadelphia, PA, United States: Society for Industrial and Applied Mathematics, 2026. <a href=\"https://doi.org/10.1137/1.9781611978971.225\">https://doi.org/10.1137/1.9781611978971.225</a>.","ista":"Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. 2026.Braiding Vineyards. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms. , 6240–6263.","ieee":"E. W. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “Braiding Vineyards,” in <i>Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, K. Green Larsen and B. Saha, Eds. Philadelphia, PA, United States: Society for Industrial and Applied Mathematics, 2026, pp. 6240–6263.","mla":"Chambers, Erin W., et al. “Braiding Vineyards.” <i>Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, edited by Kasper Green Larsen and Barna Saha, Society for Industrial and Applied Mathematics, 2026, pp. 6240–63, doi:<a href=\"https://doi.org/10.1137/1.9781611978971.225\">10.1137/1.9781611978971.225</a>.","short":"E.W. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, in:, K. Green Larsen, B. Saha (Eds.), Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, United States, 2026, pp. 6240–6263."},"quality_controlled":"1","OA_type":"green","date_published":"2026-01-07T00:00:00Z","publication":"Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"In this work, we introduce and study what we believe is an intriguing, and, to the best of our knowledge, previously unknown connection between two fundamental areas in computational topology, namely topological data analysis (TDA) and knot theory. Given a function from a topological space to ℝ, TDA provides tools to simplify and study the importance of topological features: in particular, the 𝑙^𝑡⁢ℎ-dimensional persistence diagram encodes the topological changes (or 𝑙-homology) in the sublevel set as the function value increases into a set of points in the plane. Given a continuous one parameter family of such functions, we can combine the persistence diagrams into an object known as a vineyard, which tracks the evolution of points in the persistence diagram as the function changes. If we further restrict that family of functions to be periodic, we identify the two ends of the vineyard, yielding a closed vineyard. This allows the study of monodromy, which in this context means that following the family of functions for a period permutes the set of points in a non-trivial way. Recent work has studied monodromy in the directional persistent homology transform, demonstrating some interesting connections between an input shape and monodromy in the persistent homology transform for 0-dimensional homology embedded in ℝ^2.\r\nIn this work, given a link and a value 𝑙, we construct a topological space (based on the given link) and periodic family of functions on this space (based on the Euclidean distance function), such that the closed 𝑙-vineyard contains this link. This shows that vineyards are topologically as rich as one could possibly hope, suggesting many future directions of work. Importantly, it has at least two immediate consequences we explicitly point out:\r\n1.\tMonodromy of any periodicity can occur in a 𝑙-vineyard for any 𝑙. This answers a variant of a question by Arya and collaborators. To exhibit this as a consequence of our first main result we also reformulate monodromy in a more geometric way, which may be of interest in itself.\r\n2.\tTopologically distinguishing closed vineyards is likely to be difficult (from a complexity theory as well as from a practical perspective) because of the difficulty of knot and link recognition, which have strong connections to many NP-hard problems.","lang":"eng"}],"date_updated":"2026-02-16T08:06:23Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2504.11203"}],"date_created":"2026-01-28T12:58:16Z","external_id":{"arxiv":["2504.11203"]},"title":"Braiding Vineyards","author":[{"full_name":"Chambers, Erin W.","first_name":"Erin W.","last_name":"Chambers"},{"first_name":"Christopher D","last_name":"Fillmore","full_name":"Fillmore, Christopher D","id":"35638A5C-AAC7-11E9-B0BF-5503E6697425"},{"orcid":"0000-0002-6862-208X","last_name":"Stephenson","first_name":"Elizabeth R","full_name":"Stephenson, Elizabeth R","id":"2D04F932-F248-11E8-B48F-1D18A9856A87"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220"}]},{"date_updated":"2026-04-07T11:42:48Z","arxiv":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2504.11203","open_access":"1"}],"abstract":[{"text":"In this work, we introduce and study what we believe is an intriguing and, to the best of our knowledge, previously unknown connection between two areas in computational topology, topological data analysis (TDA) and knot theory. Given a function from a topological space to $\\mathbb{R}$, TDA provides tools to simplify and study the importance of topological features: in particular, the $l^{th}$-dimensional persistence diagram encodes the $l$-homology in the sublevel set as the function value increases as a set of points in the plane. Given a continuous one-parameter family of such functions, we can combine the persistence diagrams into an object known as a vineyard, which track the evolution of points in the persistence diagram. If we further restrict that family of functions to be periodic, we identify the two ends of the vineyard, yielding a closed vineyard. This allows the study of monodromy, which in this context means that following the family of functions for a period permutes the set of points in a non-trivial way. In this work, given a link and value $l$, we construct a topological space and periodic family of functions such that the closed $l$-vineyard contains this link. This shows that vineyards are topologically as rich as one could possibly hope. Importantly, it has at least two immediate consequences: First, monodromy of any periodicity can occur in a $l$-vineyard, answering a variant of a question by [Arya et al 2024]. To exhibit this, we also reformulate monodromy in a more geometric way, which may be of interest in itself. Second, distinguishing vineyards is likely to be difficult given the known difficulty of knot and link recognition, which have strong connections to many NP-hard problems.","lang":"eng"}],"month":"01","external_id":{"arxiv":["2504.11203"]},"date_created":"2026-01-27T14:41:44Z","title":"Braiding vineyards","author":[{"full_name":" Chambers, Erin","first_name":"Erin","last_name":" Chambers"},{"id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","full_name":"Fillmore, Christopher D","last_name":"Fillmore","first_name":"Christopher D"},{"id":"2D04F932-F248-11E8-B48F-1D18A9856A87","full_name":"Stephenson, Elizabeth R","orcid":"0000-0002-6862-208X","first_name":"Elizabeth R","last_name":"Stephenson"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220"}],"date_published":"2026-01-02T00:00:00Z","doi":"10.48550/ARXIV.2504.11203","corr_author":"1","related_material":{"record":[{"status":"public","id":"21056","relation":"later_version"},{"relation":"dissertation_contains","status":"public","id":"21021"}]},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","year":"2026","oa":1,"publication_status":"draft","language":[{"iso":"eng"}],"publication":"arXiv","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"status":"public","OA_place":"repository","citation":{"apa":"Chambers, E., Fillmore, C. D., Stephenson, E. R., &#38; Wintraecken, M. (n.d.). Braiding vineyards. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/ARXIV.2504.11203\">https://doi.org/10.48550/ARXIV.2504.11203</a>","ama":"Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. Braiding vineyards. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/ARXIV.2504.11203\">10.48550/ARXIV.2504.11203</a>","chicago":"Chambers, Erin, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs Wintraecken. “Braiding Vineyards.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/ARXIV.2504.11203\">https://doi.org/10.48550/ARXIV.2504.11203</a>.","ista":"Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. Braiding vineyards. arXiv, <a href=\"https://doi.org/10.48550/ARXIV.2504.11203\">10.48550/ARXIV.2504.11203</a>.","ieee":"E.  Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “Braiding vineyards,” <i>arXiv</i>. .","mla":"Chambers, Erin, et al. “Braiding Vineyards.” <i>ArXiv</i>, doi:<a href=\"https://doi.org/10.48550/ARXIV.2504.11203\">10.48550/ARXIV.2504.11203</a>.","short":"E.  Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, ArXiv (n.d.)."},"day":"02","type":"preprint","_id":"21051","article_processing_charge":"No","oa_version":"Preprint","department":[{"_id":"HeEd"}]},{"month":"12","language":[{"iso":"eng"}],"file":[{"file_name":"2025_LaMatematica_Chambers.pdf","date_updated":"2025-12-30T07:52:58Z","file_size":2678640,"content_type":"application/pdf","checksum":"e2043259194bfcdf3d74c4da8a5a853f","date_created":"2025-12-30T07:52:58Z","relation":"main_file","access_level":"open_access","creator":"dernst","success":1,"file_id":"20885"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2025","oa":1,"doi":"10.1007/s44007-025-00170-0","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"21021"}]},"page":"811-828","PlanS_conform":"1","has_accepted_license":"1","volume":4,"OA_place":"publisher","status":"public","ec_funded":1,"publication_identifier":{"eissn":["2730-9657"]},"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.","type":"journal_article","date_created":"2025-08-31T22:01:33Z","author":[{"full_name":"Chambers, Erin Wolf","last_name":"Chambers","first_name":"Erin Wolf"},{"full_name":"Fillmore, Christopher D","id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","first_name":"Christopher D","last_name":"Fillmore"},{"full_name":"Stephenson, Elizabeth R","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6862-208X","first_name":"Elizabeth R","last_name":"Stephenson"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs"}],"title":"Burning or collapsing the medial axis is unstable","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses","grant_number":"M03073"}],"abstract":[{"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.","lang":"eng"}],"date_updated":"2026-04-07T11:42:48Z","file_date_updated":"2025-12-30T07:52:58Z","publication":"La Matematica","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","corr_author":"1","OA_type":"hybrid","date_published":"2025-12-01T00:00:00Z","ddc":["510"],"citation":{"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.” <i>La Matematica</i>, vol. 4, Springer Nature, 2025, pp. 811–28, doi:<a href=\"https://doi.org/10.1007/s44007-025-00170-0\">10.1007/s44007-025-00170-0</a>.","short":"E.W. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, La Matematica 4 (2025) 811–828.","ieee":"E. W. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “Burning or collapsing the medial axis is unstable,” <i>La Matematica</i>, vol. 4. Springer Nature, pp. 811–828, 2025.","ama":"Chambers EW, Fillmore CD, Stephenson ER, Wintraecken M. Burning or collapsing the medial axis is unstable. <i>La Matematica</i>. 2025;4:811-828. doi:<a href=\"https://doi.org/10.1007/s44007-025-00170-0\">10.1007/s44007-025-00170-0</a>","apa":"Chambers, E. W., Fillmore, C. D., Stephenson, E. R., &#38; Wintraecken, M. (2025). Burning or collapsing the medial axis is unstable. <i>La Matematica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s44007-025-00170-0\">https://doi.org/10.1007/s44007-025-00170-0</a>","chicago":"Chambers, Erin Wolf, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs Wintraecken. “Burning or Collapsing the Medial Axis Is Unstable.” <i>La Matematica</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s44007-025-00170-0\">https://doi.org/10.1007/s44007-025-00170-0</a>."},"quality_controlled":"1","publisher":"Springer Nature","intvolume":"         4","department":[{"_id":"HeEd"}],"article_type":"original","scopus_import":"1","_id":"20260","oa_version":"Published Version","article_processing_charge":"Yes (via OA deal)","day":"01"},{"date_published":"2024-06-06T00:00:00Z","corr_author":"1","article_number":"87","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2024-09-19T10:30:37Z","publication":"40th International Symposium on Computational Geometry","date_updated":"2025-04-15T07:16:58Z","abstract":[{"lang":"eng","text":"In our companion paper \"Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds\" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting."}],"project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_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","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35"},{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"title":"The ultimate frontier: An optimality construction for homotopy inference (media exposition)","author":[{"first_name":"Dominique","last_name":"Attali","full_name":"Attali, Dominique"},{"first_name":"Hana","last_name":"Kourimska","orcid":"0000-0001-7841-0091","full_name":"Kourimska, Hana","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E"},{"id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","full_name":"Fillmore, Christopher D","first_name":"Christopher D","last_name":"Fillmore"},{"first_name":"Ishika","last_name":"Ghosh","id":"ee449b28-344d-11ef-a6d5-9ca430e9e9ff","full_name":"Ghosh, Ishika"},{"first_name":"Andre","last_name":"Lieutier","full_name":"Lieutier, Andre"},{"full_name":"Stephenson, Elizabeth R","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","last_name":"Stephenson","first_name":"Elizabeth R","orcid":"0000-0002-6862-208X"},{"first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2024-09-19T10:29:48Z","day":"06","oa_version":"Published Version","article_processing_charge":"Yes","_id":"18097","department":[{"_id":"HeEd"}],"alternative_title":["LIPIcs"],"intvolume":"       293","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","citation":{"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.","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.","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>.","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.","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>","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>","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>."},"ddc":["000"],"conference":{"start_date":"2024-06-11","end_date":"2024-06-14","location":"Athens, Greece","name":"SoCG: Symposium on Computational Geometry"},"has_accepted_license":"1","doi":"10.4230/LIPIcs.SoCG.2024.87","oa":1,"year":"2024","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"file_id":"18098","access_level":"open_access","success":1,"creator":"dernst","date_created":"2024-09-19T10:30:37Z","relation":"main_file","content_type":"application/pdf","file_size":3507177,"checksum":"9355c2e60b8ec285e1b22719c5b73f1a","file_name":"2024_LIPICs_Attali.pdf","date_updated":"2024-09-19T10:30:37Z"}],"language":[{"iso":"eng"}],"month":"06","type":"conference","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.","publication_identifier":{"isbn":["9783959773164"]},"ec_funded":1,"status":"public","volume":293},{"quality_controlled":"1","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: <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>","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>","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>.","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.","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>.","short":"H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"ddc":["510"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","scopus_import":"1","department":[{"_id":"HeEd"}],"alternative_title":["LIPIcs"],"intvolume":"       293","day":"01","article_processing_charge":"No","oa_version":"Published Version","_id":"17144","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"_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","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"title":"The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms","author":[{"last_name":"Kourimska","first_name":"Hana","orcid":"0000-0001-7841-0091","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","full_name":"Kourimska, Hana"},{"full_name":"Lieutier, André","last_name":"Lieutier","first_name":"André"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"date_created":"2024-06-16T22:01:06Z","external_id":{"arxiv":["2212.01118"]},"date_updated":"2025-04-15T07:16:58Z","abstract":[{"lang":"eng","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."}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"40th International Symposium on Computational Geometry","file_date_updated":"2024-06-17T08:33:40Z","date_published":"2024-06-01T00:00:00Z","article_number":"69","volume":293,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773164"]},"ec_funded":1,"status":"public","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.","type":"conference","month":"06","arxiv":1,"oa":1,"year":"2024","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"file_name":"2024_LIPICS_Kourimska.pdf","date_updated":"2024-06-17T08:33:40Z","checksum":"b40ff456c19294adb5d9613fcfd751c6","content_type":"application/pdf","file_size":1612558,"relation":"main_file","date_created":"2024-06-17T08:33:40Z","creator":"dernst","success":1,"access_level":"open_access","file_id":"17150"}],"language":[{"iso":"eng"}],"conference":{"location":"Athens, Greece","end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry"},"has_accepted_license":"1","doi":"10.4230/LIPIcs.SoCG.2024.69"},{"project":[{"call_identifier":"H2020","grant_number":"788183","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Mathematics, Computer Science","grant_number":"Z00342"},{"call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"},{"name":"Learning and triangulating manifolds via collapses","grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"}],"title":"Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds","author":[{"full_name":"Attali, Dominique","first_name":"Dominique","last_name":"Attali"},{"orcid":"0000-0001-7841-0091","first_name":"Hana","last_name":"Kourimska","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","full_name":"Kourimska, Hana"},{"full_name":"Fillmore, Christopher D","id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","first_name":"Christopher D","last_name":"Fillmore"},{"first_name":"Ishika","last_name":"Ghosh","full_name":"Ghosh, Ishika","id":"ee449b28-344d-11ef-a6d5-9ca430e9e9ff"},{"first_name":"André","last_name":"Lieutier","full_name":"Lieutier, André"},{"orcid":"0000-0002-6862-208X","last_name":"Stephenson","first_name":"Elizabeth R","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","full_name":"Stephenson, Elizabeth R"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220"}],"external_id":{"arxiv":["2206.10485"]},"date_created":"2024-06-25T11:45:58Z","date_updated":"2025-04-15T07:16:57Z","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"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2024-06-25T11:47:26Z","publication":"40th International Symposium on Computational Geometry","date_published":"2024-06-06T00:00:00Z","quality_controlled":"1","citation":{"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.","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.","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>.","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>","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>","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>."},"ddc":["516"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","scopus_import":"1","department":[{"_id":"GradSch"},{"_id":"HeEd"}],"alternative_title":["LIPIcs"],"intvolume":"       293","day":"06","oa_version":"Published Version","article_processing_charge":"No","_id":"17170","month":"06","arxiv":1,"oa":1,"year":"2024","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"file_id":"17171","access_level":"open_access","creator":"cfillmor","success":1,"date_created":"2024-06-25T11:47:26Z","relation":"main_file","file_name":"LIPIcs.SoCG.2024.11.pdf","date_updated":"2024-06-25T11:47:26Z","checksum":"6a2ddc8b51aa58f197a8b294750f1f8d","content_type":"application/pdf","file_size":20886142}],"page":"11:1-11:19","has_accepted_license":"1","conference":{"name":"SoCG: Symposium on Computational Geometry","location":"Athens, Greece","end_date":"2024-06-14","start_date":"2024-06-11"},"doi":"10.4230/LIPIcs.SoCG.2024.11","volume":293,"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773164"]},"ec_funded":1,"status":"public","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.","type":"conference"},{"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2204.01077","open_access":"1"}],"date_updated":"2025-09-08T08:06:04Z","abstract":[{"text":"For a locally finite set, 𝐴⊆ℝ𝑑\r\n, the 𝑘\r\nth Brillouin zone of 𝑎∈𝐴\r\n is the region of points 𝑥∈ℝ𝑑\r\n for which ‖𝑥−𝑎‖\r\n is the 𝑘\r\nth smallest among the Euclidean distances between 𝑥\r\n and the points in 𝐴\r\n. If 𝐴\r\n is a lattice, the 𝑘\r\nth Brillouin zones of the points in 𝐴\r\n are translates of each other, and together they tile space. Depending on the value of 𝑘\r\n, they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in ℝ2\r\n, and the convergence of the maximum volume of a chamber to zero for the integer lattice.","lang":"eng"}],"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"},{"name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","name":"Mathematics, Computer Science","call_identifier":"FWF"}],"title":"Brillouin zones of integer lattices and their perturbations","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Garber, Alexey","last_name":"Garber","first_name":"Alexey"},{"last_name":"Ghafaris","first_name":"Mohadese","full_name":"Ghafaris, Mohadese"},{"id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","full_name":"Heiss, Teresa","orcid":"0000-0002-1780-2689","first_name":"Teresa","last_name":"Heiss"},{"last_name":"Saghafiant","first_name":"Morteza","full_name":"Saghafiant, Morteza"},{"orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"date_created":"2024-06-30T22:01:05Z","external_id":{"isi":["001292728600001"],"arxiv":["2204.01077"]},"date_published":"2024-06-07T00:00:00Z","corr_author":"1","publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"SIAM Journal on Discrete Mathematics","publisher":"Society for Industrial and Applied Mathematics","citation":{"apa":"Edelsbrunner, H., Garber, A., Ghafaris, M., Heiss, T., Saghafiant, M., &#38; Wintraecken, M. (2024). Brillouin zones of integer lattices and their perturbations. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/22M1489071\">https://doi.org/10.1137/22M1489071</a>","ama":"Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M. Brillouin zones of integer lattices and their perturbations. <i>SIAM Journal on Discrete Mathematics</i>. 2024;38(2):1784-1807. doi:<a href=\"https://doi.org/10.1137/22M1489071\">10.1137/22M1489071</a>","chicago":"Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafaris, Teresa Heiss, Morteza Saghafiant, and Mathijs Wintraecken. “Brillouin Zones of Integer Lattices and Their Perturbations.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/22M1489071\">https://doi.org/10.1137/22M1489071</a>.","ista":"Edelsbrunner H, Garber A, Ghafaris M, Heiss T, Saghafiant M, Wintraecken M. 2024. Brillouin zones of integer lattices and their perturbations. SIAM Journal on Discrete Mathematics. 38(2), 1784–1807.","ieee":"H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, and M. Wintraecken, “Brillouin zones of integer lattices and their perturbations,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 38, no. 2. Society for Industrial and Applied Mathematics, pp. 1784–1807, 2024.","mla":"Edelsbrunner, Herbert, et al. “Brillouin Zones of Integer Lattices and Their Perturbations.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 38, no. 2, Society for Industrial and Applied Mathematics, 2024, pp. 1784–807, doi:<a href=\"https://doi.org/10.1137/22M1489071\">10.1137/22M1489071</a>.","short":"H. Edelsbrunner, A. Garber, M. Ghafaris, T. Heiss, M. Saghafiant, M. Wintraecken, SIAM Journal on Discrete Mathematics 38 (2024) 1784–1807."},"quality_controlled":"1","day":"07","oa_version":"Preprint","article_processing_charge":"No","_id":"17190","article_type":"original","scopus_import":"1","department":[{"_id":"HeEd"}],"intvolume":"        38","arxiv":1,"isi":1,"month":"06","page":"1784-1807","doi":"10.1137/22M1489071","issue":"2","oa":1,"year":"2024","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0895-4801"]},"ec_funded":1,"status":"public","volume":38,"type":"journal_article","acknowledgement":"The second author is partially supported by the Alexander von Humboldt Foundation. The sixth author is supported by the European Union's Horizon 2020 research and innovation programme under Marie Sklodowska-Curie grant agreement 754411, and by Austrian Science Fund(FWF) grant M-3073. All other authors are supported by European Research Council (ERC) grant 788183, by the Wittgenstein Prize, by Austrian Science Fund (FWF) grant Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF) grant I 02979-N35."},{"ddc":["510"],"quality_controlled":"1","citation":{"ista":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating general manifolds. Discrete &#38; Computational Geometry. 69, 156–191.","mla":"Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 156–91, doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete &#38; Computational Geometry 69 (2023) 156–191.","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for triangulating general manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 69. Springer Nature, pp. 156–191, 2023.","apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., &#38; Wintraecken, M. (2023). Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>","ama":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. 2023;69:156-191. doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>."},"publisher":"Springer Nature","department":[{"_id":"HeEd"}],"intvolume":"        69","article_type":"original","scopus_import":"1","article_processing_charge":"No","oa_version":"Published Version","_id":"12287","day":"01","author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"full_name":"Dyer, Ramsay","last_name":"Dyer","first_name":"Ramsay"},{"full_name":"Ghosh, Arijit","first_name":"Arijit","last_name":"Ghosh"},{"orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"title":"Local criteria for triangulating general manifolds","external_id":{"isi":["000862193600001"]},"date_created":"2023-01-16T10:04:06Z","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"abstract":[{"lang":"eng","text":"We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use."}],"date_updated":"2025-04-14T07:44:00Z","publication":"Discrete & Computational Geometry","file_date_updated":"2023-02-02T11:01:10Z","publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","corr_author":"1","date_published":"2023-01-01T00:00:00Z","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"volume":69,"ec_funded":1,"status":"public","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian Science Fund (FWF): M-3073. A part of the results described in this paper were presented at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science Fund (FWF).","type":"journal_article","month":"01","isi":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","creator":"dernst","success":1,"file_id":"12488","date_updated":"2023-02-02T11:01:10Z","file_name":"2023_DiscreteCompGeometry_Boissonnat.pdf","checksum":"46352e0ee71e460848f88685ca852681","content_type":"application/pdf","file_size":582850,"date_created":"2023-02-02T11:01:10Z","relation":"main_file"}],"oa":1,"year":"2023","page":"156-191","has_accepted_license":"1","doi":"10.1007/s00454-022-00431-7"},{"day":"01","oa_version":"Submitted Version","article_processing_charge":"No","_id":"12763","article_type":"original","scopus_import":"1","department":[{"_id":"HeEd"}],"intvolume":"         7","publisher":"Springer Nature","citation":{"chicago":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” <i>Journal of Applied and Computational Topology</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s41468-023-00116-x\">https://doi.org/10.1007/s41468-023-00116-x</a>.","apa":"Boissonnat, J. D., &#38; Wintraecken, M. (2023). The reach of subsets of manifolds. <i>Journal of Applied and Computational Topology</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s41468-023-00116-x\">https://doi.org/10.1007/s41468-023-00116-x</a>","ama":"Boissonnat JD, Wintraecken M. The reach of subsets of manifolds. <i>Journal of Applied and Computational Topology</i>. 2023;7:619-641. doi:<a href=\"https://doi.org/10.1007/s41468-023-00116-x\">10.1007/s41468-023-00116-x</a>","ieee":"J. D. Boissonnat and M. Wintraecken, “The reach of subsets of manifolds,” <i>Journal of Applied and Computational Topology</i>, vol. 7. Springer Nature, pp. 619–641, 2023.","mla":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” <i>Journal of Applied and Computational Topology</i>, vol. 7, Springer Nature, 2023, pp. 619–41, doi:<a href=\"https://doi.org/10.1007/s41468-023-00116-x\">10.1007/s41468-023-00116-x</a>.","short":"J.D. Boissonnat, M. Wintraecken, Journal of Applied and Computational Topology 7 (2023) 619–641.","ista":"Boissonnat JD, Wintraecken M. 2023. The reach of subsets of manifolds. Journal of Applied and Computational Topology. 7, 619–641."},"quality_controlled":"1","date_published":"2023-09-01T00:00:00Z","corr_author":"1","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Journal of Applied and Computational Topology","main_file_link":[{"open_access":"1","url":"https://inserm.hal.science/INRIA-SACLAY/hal-04083524v1"}],"date_updated":"2025-04-14T07:44:01Z","abstract":[{"text":"Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift 176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert showed that sets of positive reach in Euclidean space and Riemannian manifolds are very similar. In this paper we introduce a slight variant of Kleinjohann’s and Bangert’s extension and quantify the similarity between sets of positive reach in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we bound the local feature size (a local version of the reach) of its lifting to the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated by the importance of the reach and local feature size to manifold learning, topological inference, and triangulating manifolds and the fact that intrinsic approaches circumvent the curse of dimensionality.","lang":"eng"}],"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses","grant_number":"M03073"}],"author":[{"last_name":"Boissonnat","first_name":"Jean Daniel","full_name":"Boissonnat, Jean Daniel"},{"last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"title":"The reach of subsets of manifolds","date_created":"2023-03-26T22:01:08Z","type":"journal_article","acknowledgement":"We thank Eddie Aamari, David Cohen-Steiner, Isa Costantini, Fred Chazal, Ramsay Dyer, André Lieutier, and Alef Sterk for discussion and Pierre Pansu for encouragement. We further acknowledge the anonymous reviewers whose comments helped improve the exposition.\r\nThe research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions). The first author is further supported by the French government, through the 3IA Côte d’Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002. The second author is supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411 and the Austrian science fund (FWF) M-3073.","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"ec_funded":1,"status":"public","volume":7,"page":"619-641","doi":"10.1007/s41468-023-00116-x","oa":1,"year":"2023","language":[{"iso":"eng"}],"month":"09"},{"acknowledgement":"The authors have received funding from the European Research Council under the European Union's ERC grant greement 339025 GUDHI (Algorithmic Foundations of Geometric Un-derstanding  in  Higher  Dimensions).   The  first  author  was  supported  by  the  French  government,through the 3IA C\\^ote d'Azur Investments in the Future project managed by the National ResearchAgency (ANR) with the reference ANR-19-P3IA-0002.  The third author was supported by the Eu-ropean Union's Horizon 2020 research and innovation programme under the Marie Sk\\lodowska-Curiegrant agreement 754411 and the FWF (Austrian Science Fund) grant M 3073.","type":"journal_article","volume":52,"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"status":"public","ec_funded":1,"year":"2023","oa":1,"language":[{"iso":"eng"}],"issue":"2","doi":"10.1137/21M1412918","page":"452-486","related_material":{"record":[{"relation":"earlier_version","id":"9441","status":"public"}]},"month":"04","isi":1,"article_type":"original","scopus_import":"1","intvolume":"        52","department":[{"_id":"HeEd"}],"day":"30","_id":"12960","article_processing_charge":"No","oa_version":"Submitted Version","citation":{"apa":"Boissonnat, J. D., Kachanovich, S., &#38; Wintraecken, M. (2023). Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/21M1412918\">https://doi.org/10.1137/21M1412918</a>","ama":"Boissonnat JD, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. <i>SIAM Journal on Computing</i>. 2023;52(2):452-486. doi:<a href=\"https://doi.org/10.1137/21M1412918\">10.1137/21M1412918</a>","chicago":"Boissonnat, Jean Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/21M1412918\">https://doi.org/10.1137/21M1412918</a>.","ista":"Boissonnat JD, Kachanovich S, Wintraecken M. 2023. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. 52(2), 452–486.","short":"J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing 52 (2023) 452–486.","mla":"Boissonnat, Jean Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” <i>SIAM Journal on Computing</i>, vol. 52, no. 2, Society for Industrial and Applied Mathematics, 2023, pp. 452–86, doi:<a href=\"https://doi.org/10.1137/21M1412918\">10.1137/21M1412918</a>.","ieee":"J. D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations,” <i>SIAM Journal on Computing</i>, vol. 52, no. 2. Society for Industrial and Applied Mathematics, pp. 452–486, 2023."},"quality_controlled":"1","publisher":"Society for Industrial and Applied Mathematics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","publication":"SIAM Journal on Computing","date_published":"2023-04-30T00:00:00Z","corr_author":"1","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"},{"name":"Learning and triangulating manifolds via collapses","grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"}],"date_created":"2023-05-14T22:01:00Z","external_id":{"isi":["001013183000012"]},"author":[{"full_name":"Boissonnat, Jean Daniel","first_name":"Jean Daniel","last_name":"Boissonnat"},{"full_name":"Kachanovich, Siargey","first_name":"Siargey","last_name":"Kachanovich"},{"first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations","date_updated":"2025-04-15T06:54:46Z","main_file_link":[{"open_access":"1","url":"https://hal-emse.ccsd.cnrs.fr/3IA-COTEDAZUR/hal-04083489v1"}],"abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider its piecewise linear (PL) approximation M^\r\n based on a triangulation T of the ambient space Rd. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ=1/D (and unavoidably exponential in n). Since it is known that for δ=Ω(d2.5), M^ is O(D2)-close and isotopic to M\r\n, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M^ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. ","lang":"eng"}]},{"status":"public","ec_funded":1,"publication_identifier":{"isbn":["9781450399135"]},"type":"conference","acknowledgement":"We are greatly indebted to Erin Chambers for posing a number of questions that eventually led to this paper. We would also like to thank the other organizers of the workshop on ‘Algorithms\r\nfor the medial axis’. We are also indebted to Tatiana Ezubova for helping with the search for and translation of Russian literature. The second author thanks all members of the Edelsbrunner and Datashape groups for the atmosphere in which the research was conducted.\r\nThe research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions). Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411. The Austrian science fund (FWF) M-3073.","isi":1,"arxiv":1,"month":"06","doi":"10.1145/3564246.3585113","page":"1768-1776","conference":{"start_date":"2023-06-20","name":"STOC: Symposium on Theory of Computing","end_date":"2023-06-23","location":"Orlando, FL, United States"},"language":[{"iso":"eng"}],"year":"2023","oa":1,"publisher":"Association for Computing Machinery","citation":{"chicago":"Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis.” In <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>, 1768–76. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3564246.3585113\">https://doi.org/10.1145/3564246.3585113</a>.","ama":"Lieutier A, Wintraecken M. Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. In: <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2023:1768-1776. doi:<a href=\"https://doi.org/10.1145/3564246.3585113\">10.1145/3564246.3585113</a>","apa":"Lieutier, A., &#38; Wintraecken, M. (2023). Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. In <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i> (pp. 1768–1776). Orlando, FL, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3564246.3585113\">https://doi.org/10.1145/3564246.3585113</a>","short":"A. Lieutier, M. Wintraecken, in:, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2023, pp. 1768–1776.","mla":"Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis.” <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2023, pp. 1768–76, doi:<a href=\"https://doi.org/10.1145/3564246.3585113\">10.1145/3564246.3585113</a>.","ieee":"A. Lieutier and M. Wintraecken, “Hausdorff and Gromov-Hausdorff stable subsets of the medial axis,” in <i>Proceedings of the 55th Annual ACM Symposium on Theory of Computing</i>, Orlando, FL, United States, 2023, pp. 1768–1776.","ista":"Lieutier A, Wintraecken M. 2023. Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 1768–1776."},"quality_controlled":"1","_id":"13048","article_processing_charge":"No","oa_version":"Preprint","day":"02","department":[{"_id":"HeEd"}],"scopus_import":"1","abstract":[{"text":"In this paper we introduce a pruning of the medial axis called the (λ,α)-medial axis (axλα). We prove that the (λ,α)-medial axis of a set K is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if K and K′ are close in the Hausdorff (dH) sense then the (λ,α)-medial axes of K and K′ are close as metric spaces, that is the Gromov-Hausdorff distance (dGH) between the two is 1/4-Hölder in the sense that dGH (axλα(K),axλα(K′)) ≲ dH(K,K′)1/4. The Hausdorff distance between the two medial axes is also bounded, by dH (axλα(K),λα(K′)) ≲ dH(K,K′)1/2. These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis.","lang":"eng"}],"date_updated":"2025-09-09T12:26:49Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2303.04014"}],"external_id":{"arxiv":["2303.04014"],"isi":["001064640700143"]},"date_created":"2023-05-22T08:02:02Z","title":"Hausdorff and Gromov-Hausdorff stable subsets of the medial axis","author":[{"full_name":"Lieutier, André","first_name":"André","last_name":"Lieutier"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"corr_author":"1","date_published":"2023-06-02T00:00:00Z","publication":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published"},{"acknowledgement":"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”. Erin Chambers: Supported in part by the National Science Foundation through grants DBI-1759807, CCF-1907612, and CCF-2106672. 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) M-3073 Acknowledgements 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.","type":"conference","series_title":"LIPIcs","volume":224,"status":"public","ec_funded":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-227-3"]},"file":[{"file_id":"11437","creator":"dernst","success":1,"access_level":"open_access","relation":"main_file","date_created":"2022-06-07T07:58:30Z","file_name":"2022_LIPICs_Chambers.pdf","date_updated":"2022-06-07T07:58:30Z","content_type":"application/pdf","checksum":"b25ce40fade4ebc0bcaae176db4f5f1f","file_size":17580705}],"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2022","oa":1,"doi":"10.4230/LIPIcs.SoCG.2022.66","has_accepted_license":"1","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2022-06-10","location":"Berlin, Germany","start_date":"2022-06-07"},"page":"66:1-66:9","editor":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"full_name":"Kerber, Michael","first_name":"Michael","last_name":"Kerber"}],"month":"06","intvolume":"       224","department":[{"_id":"HeEd"}],"scopus_import":"1","_id":"11428","oa_version":"Published Version","article_processing_charge":"No","day":"01","ddc":["510"],"citation":{"chicago":"Chambers, Erin, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs Wintraecken. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” In <i>38th International Symposium on Computational Geometry</i>, edited by Xavier Goaoc and Michael Kerber, 224:66:1-66:9. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">https://doi.org/10.4230/LIPIcs.SoCG.2022.66</a>.","ama":"Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. A cautionary tale: Burning the medial axis is unstable. In: Goaoc X, Kerber M, eds. <i>38th International Symposium on Computational Geometry</i>. Vol 224. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:66:1-66:9. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">10.4230/LIPIcs.SoCG.2022.66</a>","apa":"Chambers, E., Fillmore, C. D., Stephenson, E. R., &#38; Wintraecken, M. (2022). A cautionary tale: Burning the medial axis is unstable. In X. Goaoc &#38; M. Kerber (Eds.), <i>38th International Symposium on Computational Geometry</i> (Vol. 224, p. 66:1-66:9). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">https://doi.org/10.4230/LIPIcs.SoCG.2022.66</a>","ieee":"E. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “A cautionary tale: Burning the medial axis is unstable,” in <i>38th International Symposium on Computational Geometry</i>, Berlin, Germany, 2022, vol. 224, p. 66:1-66:9.","mla":"Chambers, Erin, et al. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” <i>38th International Symposium on Computational Geometry</i>, edited by Xavier Goaoc and Michael Kerber, vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 66:1-66:9, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">10.4230/LIPIcs.SoCG.2022.66</a>.","short":"E. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, in:, X. Goaoc, M. Kerber (Eds.), 38th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 66:1-66:9.","ista":"Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. 2022. A cautionary tale: Burning the medial axis is unstable. 38th International Symposium on Computational Geometry. SoCG: Symposium on Computational GeometryLIPIcs vol. 224, 66:1-66:9."},"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"38th International Symposium on Computational Geometry","file_date_updated":"2022-06-07T07:58:30Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication_status":"published","corr_author":"1","date_published":"2022-06-01T00:00:00Z","date_created":"2022-06-01T14:18:04Z","title":"A cautionary tale: Burning the medial axis is unstable","author":[{"full_name":"Chambers, Erin","first_name":"Erin","last_name":"Chambers"},{"last_name":"Fillmore","first_name":"Christopher D","id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","full_name":"Fillmore, Christopher D"},{"id":"2D04F932-F248-11E8-B48F-1D18A9856A87","full_name":"Stephenson, Elizabeth R","last_name":"Stephenson","first_name":"Elizabeth R","orcid":"0000-0002-6862-208X"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs"}],"project":[{"grant_number":"M03073","name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"},{"grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"abstract":[{"text":"The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. 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. 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, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.","lang":"eng"}],"date_updated":"2025-04-14T07:43:57Z"},{"month":"01","isi":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"date_created":"2021-07-14T06:44:36Z","relation":"main_file","date_updated":"2021-07-14T06:44:36Z","file_name":"Boissonnat-Wintraecken2021_Article_TheTopologicalCorrectnessOfPLA.pdf","content_type":"application/pdf","file_size":1455699,"checksum":"f1d372ec3c08ec22e84f8e93e1126b8c","file_id":"9650","access_level":"open_access","creator":"mwintrae"}],"language":[{"iso":"eng"}],"oa":1,"year":"2022","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"7952"}]},"page":"967-1012","has_accepted_license":"1","doi":"10.1007/s10208-021-09520-0","volume":22,"ec_funded":1,"status":"public","publication_identifier":{"eissn":["1615-3383"]},"acknowledgement":"First and foremost, we acknowledge Siargey Kachanovich for discussions. We thank Herbert Edelsbrunner and all members of his group, all former and current members of the Datashape team (formerly known as Geometrica), and André Lieutier for encouragement. We further thank the reviewers of Foundations of Computational Mathematics and the reviewers and program committee of the Symposium on Computational Geometry for their feedback, which improved the exposition.\r\nThis work was funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). This work was also supported by the French government, through the 3IA Côte d’Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002. Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement no. 754411.","type":"journal_article","title":"The topological correctness of PL approximations of isomanifolds","author":[{"first_name":"Jean-Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean-Daniel"},{"first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"isi":["000673039600001"]},"date_created":"2021-07-14T06:44:53Z","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f : Rd → Rd−n. A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation T of the ambient space Rd. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently\r\nfine triangulation T . This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary.","lang":"eng"}],"date_updated":"2025-04-22T13:45:18Z","publication":"Foundations of Computational Mathematics ","file_date_updated":"2021-07-14T06:44:36Z","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","date_published":"2022-01-01T00:00:00Z","ddc":["516"],"quality_controlled":"1","citation":{"ista":"Boissonnat J-D, Wintraecken M. 2022. The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . 22, 967–1012.","short":"J.-D. Boissonnat, M. Wintraecken, Foundations of Computational Mathematics  22 (2022) 967–1012.","mla":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL Approximations of Isomanifolds.” <i>Foundations of Computational Mathematics </i>, vol. 22, Springer Nature, 2022, pp. 967–1012, doi:<a href=\"https://doi.org/10.1007/s10208-021-09520-0\">10.1007/s10208-021-09520-0</a>.","ieee":"J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL approximations of isomanifolds,” <i>Foundations of Computational Mathematics </i>, vol. 22. Springer Nature, pp. 967–1012, 2022.","ama":"Boissonnat J-D, Wintraecken M. The topological correctness of PL approximations of isomanifolds. <i>Foundations of Computational Mathematics </i>. 2022;22:967-1012. doi:<a href=\"https://doi.org/10.1007/s10208-021-09520-0\">10.1007/s10208-021-09520-0</a>","apa":"Boissonnat, J.-D., &#38; Wintraecken, M. (2022). The topological correctness of PL approximations of isomanifolds. <i>Foundations of Computational Mathematics </i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-021-09520-0\">https://doi.org/10.1007/s10208-021-09520-0</a>","chicago":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL Approximations of Isomanifolds.” <i>Foundations of Computational Mathematics </i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s10208-021-09520-0\">https://doi.org/10.1007/s10208-021-09520-0</a>."},"publisher":"Springer Nature","department":[{"_id":"HeEd"}],"intvolume":"        22","article_type":"original","scopus_import":"1","article_processing_charge":"Yes (via OA deal)","oa_version":"Published Version","_id":"9649","day":"01"},{"month":"09","isi":1,"oa":1,"year":"2021","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"page":"666-686","has_accepted_license":"1","doi":"10.1007/s00454-020-00233-9","volume":66,"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"ec_funded":1,"status":"public","acknowledgement":"Open access funding provided by the Institute of Science and Technology (IST Austria). Arijit Ghosh is supported by the Ramanujan Fellowship (No. SB/S2/RJN-064/2015), India.\r\nThis work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). The third author is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015), India. The fifth author also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411.","type":"journal_article","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020"}],"author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"full_name":"Dyer, Ramsay","first_name":"Ramsay","last_name":"Dyer"},{"first_name":"Arijit","last_name":"Ghosh","full_name":"Ghosh, Arijit"},{"first_name":"Andre","last_name":"Lieutier","full_name":"Lieutier, Andre"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"title":"Local conditions for triangulating submanifolds of Euclidean space","external_id":{"isi":["000558119300001"]},"date_created":"2020-08-11T07:11:51Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00454-020-00233-9"}],"date_updated":"2025-04-14T07:44:05Z","abstract":[{"text":"We consider the following setting: suppose that we are given a manifold M in Rd with positive reach. Moreover assume that we have an embedded simplical complex A without boundary, whose vertex set lies on the manifold, is sufficiently dense and such that all simplices in A have sufficient quality. We prove that if, locally, interiors of the projection of the simplices onto the tangent space do not intersect, then A is a triangulation of the manifold, that is, they are homeomorphic.","lang":"eng"}],"publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication":"Discrete and Computational Geometry","date_published":"2021-09-01T00:00:00Z","corr_author":"1","quality_controlled":"1","citation":{"ista":"Boissonnat J-D, Dyer R, Ghosh A, Lieutier A, Wintraecken M. 2021. Local conditions for triangulating submanifolds of Euclidean space. Discrete and Computational Geometry. 66, 666–686.","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, and M. Wintraecken, “Local conditions for triangulating submanifolds of Euclidean space,” <i>Discrete and Computational Geometry</i>, vol. 66. Springer Nature, pp. 666–686, 2021.","mla":"Boissonnat, Jean-Daniel, et al. “Local Conditions for Triangulating Submanifolds of Euclidean Space.” <i>Discrete and Computational Geometry</i>, vol. 66, Springer Nature, 2021, pp. 666–86, doi:<a href=\"https://doi.org/10.1007/s00454-020-00233-9\">10.1007/s00454-020-00233-9</a>.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, M. Wintraecken, Discrete and Computational Geometry 66 (2021) 666–686.","ama":"Boissonnat J-D, Dyer R, Ghosh A, Lieutier A, Wintraecken M. Local conditions for triangulating submanifolds of Euclidean space. <i>Discrete and Computational Geometry</i>. 2021;66:666-686. doi:<a href=\"https://doi.org/10.1007/s00454-020-00233-9\">10.1007/s00454-020-00233-9</a>","apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., Lieutier, A., &#38; Wintraecken, M. (2021). Local conditions for triangulating submanifolds of Euclidean space. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-020-00233-9\">https://doi.org/10.1007/s00454-020-00233-9</a>","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, Andre Lieutier, and Mathijs Wintraecken. “Local Conditions for Triangulating Submanifolds of Euclidean Space.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00454-020-00233-9\">https://doi.org/10.1007/s00454-020-00233-9</a>."},"ddc":["510"],"publisher":"Springer Nature","article_type":"original","scopus_import":"1","department":[{"_id":"HeEd"}],"intvolume":"        66","day":"01","oa_version":"Published Version","article_processing_charge":"Yes (via OA deal)","_id":"8248"},{"publisher":"Springer Nature","quality_controlled":"1","citation":{"ista":"Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete &#38; Computational Geometry. 66(1), 386–434.","ieee":"J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Triangulating submanifolds: An elementary and quantified version of Whitney’s method,” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 1. Springer Nature, pp. 386–434, 2021.","mla":"Boissonnat, Jean-Daniel, et al. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 1, Springer Nature, 2021, pp. 386–434, doi:<a href=\"https://doi.org/10.1007/s00454-020-00250-8\">10.1007/s00454-020-00250-8</a>.","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete &#38; Computational Geometry 66 (2021) 386–434.","ama":"Boissonnat J-D, Kachanovich S, Wintraecken M. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. <i>Discrete &#38; Computational Geometry</i>. 2021;66(1):386-434. doi:<a href=\"https://doi.org/10.1007/s00454-020-00250-8\">10.1007/s00454-020-00250-8</a>","apa":"Boissonnat, J.-D., Kachanovich, S., &#38; Wintraecken, M. (2021). Triangulating submanifolds: An elementary and quantified version of Whitney’s method. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-020-00250-8\">https://doi.org/10.1007/s00454-020-00250-8</a>","chicago":"Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00454-020-00250-8\">https://doi.org/10.1007/s00454-020-00250-8</a>."},"ddc":["516"],"day":"01","_id":"8940","oa_version":"Published Version","article_processing_charge":"Yes (via OA deal)","article_type":"original","scopus_import":"1","intvolume":"        66","department":[{"_id":"HeEd"}],"date_updated":"2025-04-14T07:43:50Z","abstract":[{"lang":"eng","text":"We quantise Whitney’s construction to prove the existence of a triangulation for any C^2 manifold, so that we get an algorithm with explicit bounds. We also give a new elementary proof, which is completely geometric."}],"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020"}],"date_created":"2020-12-12T11:07:02Z","external_id":{"isi":["000597770300001"]},"author":[{"first_name":"Jean-Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean-Daniel"},{"full_name":"Kachanovich, Siargey","first_name":"Siargey","last_name":"Kachanovich"},{"last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"title":"Triangulating submanifolds: An elementary and quantified version of Whitney’s method","date_published":"2021-07-01T00:00:00Z","corr_author":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","publication":"Discrete & Computational Geometry","file_date_updated":"2021-08-06T09:52:29Z","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"status":"public","ec_funded":1,"volume":66,"keyword":["Theoretical Computer Science","Computational Theory and Mathematics","Geometry and Topology","Discrete Mathematics and Combinatorics"],"type":"journal_article","acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement Number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). The third author also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411. Open access funding provided by the Institute of Science and Technology (IST Austria).","isi":1,"month":"07","issue":"1","doi":"10.1007/s00454-020-00250-8","page":"386-434","has_accepted_license":"1","year":"2021","oa":1,"file":[{"relation":"main_file","date_created":"2021-08-06T09:52:29Z","content_type":"application/pdf","checksum":"c848986091e56699dc12de85adb1e39c","file_size":983307,"file_name":"2021_DescreteCompGeopmetry_Boissonnat.pdf","date_updated":"2021-08-06T09:52:29Z","file_id":"9795","success":1,"creator":"kschuh","access_level":"open_access"}],"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["005","516","514"],"quality_controlled":"1","citation":{"ieee":"J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations,” in <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, Virtual, 2021, vol. 189, p. 17:1-17:16.","mla":"Boissonnat, Jean-Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations.” <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 17:1-17:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">10.4230/LIPIcs.SoCG.2021.17</a>.","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, in:, 37th International Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2021, p. 17:1-17:16.","ista":"Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. 37th International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium on Computational GeometryLeibniz International Proceedings in Informatics (LIPIcs), LIPIcs, vol. 189, 17:1-17:16.","chicago":"Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations.” In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, 189:17:1-17:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">https://doi.org/10.4230/LIPIcs.SoCG.2021.17</a>.","ama":"Boissonnat J-D, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In: <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>. Vol 189. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:17:1-17:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">10.4230/LIPIcs.SoCG.2021.17</a>","apa":"Boissonnat, J.-D., Kachanovich, S., &#38; Wintraecken, M. (2021). Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i> (Vol. 189, p. 17:1-17:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.17\">https://doi.org/10.4230/LIPIcs.SoCG.2021.17</a>"},"_id":"9441","article_processing_charge":"No","oa_version":"Published Version","day":"02","intvolume":"       189","alternative_title":["LIPIcs"],"department":[{"_id":"HeEd"}],"scopus_import":"1","abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. submanifolds of ℝ^d defined as the zero set of some multivariate multivalued smooth function f: ℝ^d → ℝ^{d-n}, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M is to consider its Piecewise-Linear (PL) approximation M̂ based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ = 1/D (and unavoidably exponential in n). Since it is known that for δ = Ω (d^{2.5}), M̂ is O(D²)-close and isotopic to M, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M̂ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. ","lang":"eng"}],"date_updated":"2025-04-15T07:09:18Z","date_created":"2021-06-02T10:10:55Z","author":[{"first_name":"Jean-Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean-Daniel"},{"last_name":"Kachanovich","first_name":"Siargey","full_name":"Kachanovich, Siargey"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220"}],"title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations","project":[{"call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"date_published":"2021-06-02T00:00:00Z","publication":"37th International Symposium on Computational Geometry (SoCG 2021)","file_date_updated":"2021-06-02T10:22:33Z","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","publication_status":"published","status":"public","ec_funded":1,"publication_identifier":{"isbn":["978-3-95977-184-9"],"issn":["1868-8969"]},"place":"Dagstuhl, Germany","volume":189,"type":"conference","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","acknowledgement":"We thank Dominique Attali, Guilherme de Fonseca, Arijit Ghosh, Vincent Pilaud and Aurélien Alvarez for their comments and suggestions. We also acknowledge the reviewers.","month":"06","doi":"10.4230/LIPIcs.SoCG.2021.17","related_material":{"record":[{"relation":"later_version","id":"12960","status":"public"}]},"page":"17:1-17:16","has_accepted_license":"1","conference":{"start_date":"2021-06-07","end_date":"2021-06-11","location":"Virtual","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"file":[{"success":1,"creator":"mwintrae","access_level":"open_access","file_id":"9442","checksum":"c322aa48d5d35a35877896cc565705b6","content_type":"application/pdf","file_size":1972902,"date_updated":"2021-06-02T10:22:33Z","file_name":"LIPIcs-SoCG-2021-17.pdf","relation":"main_file","date_created":"2021-06-02T10:22:33Z"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"year":"2021","oa":1},{"date_published":"2021-06-02T00:00:00Z","publication_status":"published","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","publication":"37th International Symposium on Computational Geometry (SoCG 2021)","file_date_updated":"2021-04-22T08:08:14Z","date_updated":"2026-04-07T12:54:09Z","abstract":[{"lang":"eng","text":"Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction."}],"project":[{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","name":"Persistent Homology, Algorithms and Stochastic Geometry","grant_number":"I4887"},{"_id":"25C5A090-B435-11E9-9278-68D0E5697425","grant_number":"Z00312","name":"Synaptic communication in neuronal microcircuits","call_identifier":"FWF"},{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"author":[{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","full_name":"Heiss, Teresa","first_name":"Teresa","last_name":"Heiss","orcid":"0000-0002-1780-2689"},{"full_name":" Kurlin , Vitaliy","first_name":"Vitaliy","last_name":" Kurlin "},{"full_name":"Smith, Philip","first_name":"Philip","last_name":"Smith"},{"first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"title":"The density fingerprint of a periodic point set","date_created":"2021-04-22T08:09:58Z","day":"02","article_processing_charge":"No","oa_version":"Published Version","_id":"9345","scopus_import":"1","department":[{"_id":"HeEd"}],"alternative_title":["LIPIcs"],"intvolume":"       189","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ista":"Edelsbrunner H, Heiss T,  Kurlin  V, Smith P, Wintraecken M. 2021. The density fingerprint of a periodic point set. 37th International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 189, 32:1-32:16.","ieee":"H. Edelsbrunner, T. Heiss, V.  Kurlin , P. Smith, and M. Wintraecken, “The density fingerprint of a periodic point set,” in <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, Virtual, 2021, vol. 189, p. 32:1-32:16.","short":"H. Edelsbrunner, T. Heiss, V.  Kurlin , P. Smith, M. Wintraecken, in:, 37th International Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16.","mla":"Edelsbrunner, Herbert, et al. “The Density Fingerprint of a Periodic Point Set.” <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">10.4230/LIPIcs.SoCG.2021.32</a>.","apa":"Edelsbrunner, H., Heiss, T.,  Kurlin , V., Smith, P., &#38; Wintraecken, M. (2021). The density fingerprint of a periodic point set. In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i> (Vol. 189, p. 32:1-32:16). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">https://doi.org/10.4230/LIPIcs.SoCG.2021.32</a>","ama":"Edelsbrunner H, Heiss T,  Kurlin  V, Smith P, Wintraecken M. The density fingerprint of a periodic point set. In: <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:32:1-32:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">10.4230/LIPIcs.SoCG.2021.32</a>","chicago":"Edelsbrunner, Herbert, Teresa Heiss, Vitaliy  Kurlin , Philip Smith, and Mathijs Wintraecken. “The Density Fingerprint of a Periodic Point Set.” In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, 189:32:1-32:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">https://doi.org/10.4230/LIPIcs.SoCG.2021.32</a>."},"quality_controlled":"1","ddc":["004","516"],"page":"32:1-32:16","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"18667"}]},"conference":{"start_date":"2021-06-07","name":"SoCG: Symposium on Computational Geometry","end_date":"2021-06-11","location":"Virtual"},"has_accepted_license":"1","doi":"10.4230/LIPIcs.SoCG.2021.32","oa":1,"year":"2021","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"date_created":"2021-04-22T08:08:14Z","relation":"main_file","checksum":"1787baef1523d6d93753b90d0c109a6d","file_size":3117435,"content_type":"application/pdf","date_updated":"2021-04-22T08:08:14Z","file_name":"df_socg_final_version.pdf","file_id":"9346","access_level":"open_access","success":1,"creator":"mwintrae"}],"month":"06","type":"conference","acknowledgement":"The authors thank Janos Pach for insightful discussions on the topic of thispaper, Morteza Saghafian for finding the one-dimensional counterexample mentioned in Section 5,and Larry Andrews for generously sharing his crystallographic perspective.","publication_identifier":{"issn":["1868-8969"]},"ec_funded":1,"status":"public","volume":189},{"publication":"36th International Symposium on Computational Geometry","file_date_updated":"2020-07-14T12:48:06Z","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","article_number":"20:1-20:18","date_published":"2020-06-01T00:00:00Z","author":[{"last_name":"Boissonnat","first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220"}],"title":"The topological correctness of PL-approximations of isomanifolds","date_created":"2020-06-09T07:24:11Z","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"abstract":[{"lang":"eng","text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e. manifolds defined as the zero set of some multivariate vector-valued smooth function f: ℝ^d → ℝ^(d-n). A natural (and efficient) way to approximate an isomanifold is to consider its Piecewise-Linear (PL) approximation based on a triangulation 𝒯 of the ambient space ℝ^d. In this paper, we give conditions under which the PL-approximation of an isomanifold is topologically equivalent to the isomanifold. The conditions are easy to satisfy in the sense that they can always be met by taking a sufficiently fine triangulation 𝒯. This contrasts with previous results on the triangulation of manifolds where, in arbitrary dimensions, delicate perturbations are needed to guarantee topological correctness, which leads to strong limitations in practice. We further give a bound on the Fréchet distance between the original isomanifold and its PL-approximation. Finally we show analogous results for the PL-approximation of an isomanifold with boundary. "}],"date_updated":"2025-04-22T13:45:17Z","alternative_title":["LIPIcs"],"department":[{"_id":"HeEd"}],"intvolume":"       164","scopus_import":"1","article_processing_charge":"No","oa_version":"Published Version","_id":"7952","day":"01","ddc":["510"],"quality_controlled":"1","citation":{"ista":"Boissonnat J-D, Wintraecken M. 2020. The topological correctness of PL-approximations of isomanifolds. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 20:1-20:18.","ieee":"J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL-approximations of isomanifolds,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","mla":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">10.4230/LIPIcs.SoCG.2020.20</a>.","short":"J.-D. Boissonnat, M. Wintraecken, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Boissonnat J-D, Wintraecken M. The topological correctness of PL-approximations of isomanifolds. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">10.4230/LIPIcs.SoCG.2020.20</a>","apa":"Boissonnat, J.-D., &#38; Wintraecken, M. (2020). The topological correctness of PL-approximations of isomanifolds. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">https://doi.org/10.4230/LIPIcs.SoCG.2020.20</a>","chicago":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">https://doi.org/10.4230/LIPIcs.SoCG.2020.20</a>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"file_id":"7969","access_level":"open_access","creator":"dernst","date_created":"2020-06-17T10:13:34Z","relation":"main_file","checksum":"38cbfa4f5d484d267a35d44d210df044","content_type":"application/pdf","file_size":1009739,"date_updated":"2020-07-14T12:48:06Z","file_name":"2020_LIPIcsSoCG_Boissonnat.pdf"}],"oa":1,"year":"2020","has_accepted_license":"1","related_material":{"record":[{"relation":"later_version","status":"public","id":"9649"}]},"conference":{"start_date":"2020-06-22","end_date":"2020-06-26","location":"Zürich, Switzerland","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2020.20","month":"06","type":"conference","volume":164,"ec_funded":1,"status":"public","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-143-6"]}},{"page":"193-199","has_accepted_license":"1","doi":"10.1556/012.2020.57.2.1454","issue":"2","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)","image":"/images/cc_by_nc.png"},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","creator":"mwintrae","file_id":"8164","date_updated":"2020-07-24T07:09:06Z","file_name":"57-2-05_4214-1454Vegter-Wintraecken_OpenAccess_CC-BY-NC.pdf","file_size":1476072,"content_type":"application/pdf","date_created":"2020-07-24T07:09:06Z","relation":"main_file"}],"oa":1,"year":"2020","isi":1,"license":"https://creativecommons.org/licenses/by-nc/4.0/","month":"07","type":"journal_article","acknowledgement":"The authors are greatly indebted to Dror Atariah, Günther Rote and John Sullivan for discussion and suggestions. The authors also thank Jean-Daniel Boissonnat, Ramsay Dyer, David de Laat and Rien van de Weijgaert for discussion. This work has been supported in part by the European Union’s Seventh Framework Programme for Research of the\r\nEuropean Commission, under FET-Open grant number 255827 (CGL Computational Geometry Learning) and ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions), the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement number 754411,and the Austrian Science Fund (FWF): Z00342 N31.","ec_funded":1,"status":"public","publication_identifier":{"issn":["0081-6906"],"eissn":["1588-2896"]},"volume":57,"corr_author":"1","date_published":"2020-07-24T00:00:00Z","file_date_updated":"2020-07-24T07:09:06Z","publication":"Studia Scientiarum Mathematicarum Hungarica","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Fejes Tóth [3] studied approximations of smooth surfaces in three-space by piecewise flat triangular meshes with a given number of vertices on the surface that are optimal with respect to Hausdorff distance. He proves that this Hausdorff distance decreases inversely proportional with the number of vertices of the approximating mesh if the surface is convex. He also claims that this Hausdorff distance is inversely proportional to the square of the number of vertices for a specific non-convex surface, namely a one-sheeted hyperboloid of revolution bounded by two congruent circles. We refute this claim, and show that the asymptotic behavior of the Hausdorff distance is linear, that is the same as for convex surfaces.","lang":"eng"}],"date_updated":"2025-04-15T07:16:57Z","author":[{"full_name":"Vegter, Gert","first_name":"Gert","last_name":"Vegter"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220"}],"title":"Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes","external_id":{"isi":["000570978400005"]},"date_created":"2020-07-24T07:09:18Z","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","name":"Mathematics, Computer Science","call_identifier":"FWF"}],"article_processing_charge":"No","oa_version":"Published Version","_id":"8163","day":"24","department":[{"_id":"HeEd"}],"intvolume":"        57","article_type":"original","scopus_import":"1","publisher":"Akadémiai Kiadó","ddc":["510"],"citation":{"ama":"Vegter G, Wintraecken M. Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. <i>Studia Scientiarum Mathematicarum Hungarica</i>. 2020;57(2):193-199. doi:<a href=\"https://doi.org/10.1556/012.2020.57.2.1454\">10.1556/012.2020.57.2.1454</a>","apa":"Vegter, G., &#38; Wintraecken, M. (2020). Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. <i>Studia Scientiarum Mathematicarum Hungarica</i>. Akadémiai Kiadó. <a href=\"https://doi.org/10.1556/012.2020.57.2.1454\">https://doi.org/10.1556/012.2020.57.2.1454</a>","chicago":"Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes Tóth on the Accuracy of Surface Meshes.” <i>Studia Scientiarum Mathematicarum Hungarica</i>. Akadémiai Kiadó, 2020. <a href=\"https://doi.org/10.1556/012.2020.57.2.1454\">https://doi.org/10.1556/012.2020.57.2.1454</a>.","ista":"Vegter G, Wintraecken M. 2020. Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 57(2), 193–199.","mla":"Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes Tóth on the Accuracy of Surface Meshes.” <i>Studia Scientiarum Mathematicarum Hungarica</i>, vol. 57, no. 2, Akadémiai Kiadó, 2020, pp. 193–99, doi:<a href=\"https://doi.org/10.1556/012.2020.57.2.1454\">10.1556/012.2020.57.2.1454</a>.","short":"G. Vegter, M. Wintraecken, Studia Scientiarum Mathematicarum Hungarica 57 (2020) 193–199.","ieee":"G. Vegter and M. Wintraecken, “Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes,” <i>Studia Scientiarum Mathematicarum Hungarica</i>, vol. 57, no. 2. Akadémiai Kiadó, pp. 193–199, 2020."},"quality_controlled":"1"},{"article_type":"original","scopus_import":"1","intvolume":"        14","department":[{"_id":"HeEd"}],"day":"01","_id":"7567","oa_version":"Published Version","article_processing_charge":"Yes (via OA deal)","citation":{"mla":"Choudhary, Aruni, et al. “Coxeter Triangulations Have Good Quality.” <i>Mathematics in Computer Science</i>, vol. 14, Springer Nature, 2020, pp. 141–76, doi:<a href=\"https://doi.org/10.1007/s11786-020-00461-5\">10.1007/s11786-020-00461-5</a>.","short":"A. Choudhary, S. Kachanovich, M. Wintraecken, Mathematics in Computer Science 14 (2020) 141–176.","ieee":"A. Choudhary, S. Kachanovich, and M. Wintraecken, “Coxeter triangulations have good quality,” <i>Mathematics in Computer Science</i>, vol. 14. Springer Nature, pp. 141–176, 2020.","ista":"Choudhary A, Kachanovich S, Wintraecken M. 2020. Coxeter triangulations have good quality. Mathematics in Computer Science. 14, 141–176.","chicago":"Choudhary, Aruni, Siargey Kachanovich, and Mathijs Wintraecken. “Coxeter Triangulations Have Good Quality.” <i>Mathematics in Computer Science</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s11786-020-00461-5\">https://doi.org/10.1007/s11786-020-00461-5</a>.","apa":"Choudhary, A., Kachanovich, S., &#38; Wintraecken, M. (2020). Coxeter triangulations have good quality. <i>Mathematics in Computer Science</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11786-020-00461-5\">https://doi.org/10.1007/s11786-020-00461-5</a>","ama":"Choudhary A, Kachanovich S, Wintraecken M. Coxeter triangulations have good quality. <i>Mathematics in Computer Science</i>. 2020;14:141-176. doi:<a href=\"https://doi.org/10.1007/s11786-020-00461-5\">10.1007/s11786-020-00461-5</a>"},"quality_controlled":"1","ddc":["510"],"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","file_date_updated":"2020-11-20T10:18:02Z","publication":"Mathematics in Computer Science","date_published":"2020-03-01T00:00:00Z","corr_author":"1","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"},{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"date_created":"2020-03-05T13:30:18Z","author":[{"full_name":"Choudhary, Aruni","first_name":"Aruni","last_name":"Choudhary"},{"full_name":"Kachanovich, Siargey","first_name":"Siargey","last_name":"Kachanovich"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs"}],"title":"Coxeter triangulations have good quality","date_updated":"2025-04-14T07:44:03Z","abstract":[{"lang":"eng","text":"Coxeter triangulations are triangulations of Euclidean space based on a single simplex. By this we mean that given an individual simplex we can recover the entire triangulation of Euclidean space by inductively reflecting in the faces of the simplex. In this paper we establish that the quality of the simplices in all Coxeter triangulations is O(1/d−−√) of the quality of regular simplex. We further investigate the Delaunay property for these triangulations. Moreover, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space."}],"type":"journal_article","volume":14,"publication_identifier":{"eissn":["1661-8289"],"issn":["1661-8270"]},"status":"public","ec_funded":1,"year":"2020","oa":1,"file":[{"date_created":"2020-11-20T10:18:02Z","relation":"main_file","file_size":872275,"content_type":"application/pdf","checksum":"1d145f3ab50ccee735983cb89236e609","date_updated":"2020-11-20T10:18:02Z","file_name":"2020_MathCompScie_Choudhary.pdf","file_id":"8783","access_level":"open_access","success":1,"creator":"dernst"}],"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"doi":"10.1007/s11786-020-00461-5","has_accepted_license":"1","page":"141-176","month":"03"}]