[{"ec_funded":1,"year":"2023","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.","publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Association for Computing Machinery","author":[{"first_name":"André","last_name":"Lieutier","full_name":"Lieutier, André"},{"first_name":"Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs"}],"date_updated":"2023-05-22T08:15:19Z","date_created":"2023-05-22T08:02:02Z","month":"06","publication_identifier":{"isbn":["9781450399135"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2303.04014"}],"external_id":{"arxiv":["2303.04014"]},"oa":1,"quality_controlled":"1","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"conference":{"start_date":"2023-06-20","location":"Orlando, FL, United States","end_date":"2023-06-23","name":"STOC: Symposium on Theory of Computing"},"doi":"10.1145/3564246.3585113","language":[{"iso":"eng"}],"type":"conference","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"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"13048","status":"public","title":"Hausdorff and Gromov-Hausdorff stable subsets of the medial axis","oa_version":"Preprint","day":"02","article_processing_charge":"No","publication":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing","citation":{"ama":"Lieutier A, Wintraecken M. Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2023:1768-1776. doi:10.1145/3564246.3585113","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.","apa":"Lieutier, A., & Wintraecken, M. (2023). Hausdorff and Gromov-Hausdorff stable subsets of the medial axis. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1768–1776). Orlando, FL, United States: Association for Computing Machinery. https://doi.org/10.1145/3564246.3585113","ieee":"A. Lieutier and M. Wintraecken, “Hausdorff and Gromov-Hausdorff stable subsets of the medial axis,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Orlando, FL, United States, 2023, pp. 1768–1776.","mla":"Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis.” Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2023, pp. 1768–76, doi:10.1145/3564246.3585113.","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.","chicago":"Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis.” In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 1768–76. Association for Computing Machinery, 2023. https://doi.org/10.1145/3564246.3585113."},"page":"1768-1776","date_published":"2023-06-02T00:00:00Z"},{"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"01","external_id":{"isi":["000862193600001"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"isi":1,"quality_controlled":"1","doi":"10.1007/s00454-022-00431-7","language":[{"iso":"eng"}],"ec_funded":1,"file_date_updated":"2023-02-02T11:01:10Z","year":"2023","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).","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"published","author":[{"last_name":"Boissonnat","first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel"},{"full_name":"Dyer, Ramsay","first_name":"Ramsay","last_name":"Dyer"},{"full_name":"Ghosh, Arijit","last_name":"Ghosh","first_name":"Arijit"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"volume":69,"date_created":"2023-01-16T10:04:06Z","date_updated":"2023-08-01T12:47:32Z","scopus_import":"1","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"article_processing_charge":"No","has_accepted_license":"1","day":"01","citation":{"apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., & Wintraecken, M. (2023). Local criteria for triangulating general manifolds. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00431-7","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for triangulating general manifolds,” Discrete & Computational Geometry, vol. 69. Springer Nature, pp. 156–191, 2023.","ista":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating general manifolds. Discrete & Computational Geometry. 69, 156–191.","ama":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating general manifolds. Discrete & Computational Geometry. 2023;69:156-191. doi:10.1007/s00454-022-00431-7","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. “Local Criteria for Triangulating General Manifolds.” Discrete & Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00431-7.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete & Computational Geometry 69 (2023) 156–191.","mla":"Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.” Discrete & Computational Geometry, vol. 69, Springer Nature, 2023, pp. 156–91, doi:10.1007/s00454-022-00431-7."},"publication":"Discrete & Computational Geometry","page":"156-191","article_type":"original","date_published":"2023-01-01T00:00:00Z","type":"journal_article","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."}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"12287","intvolume":" 69","title":"Local criteria for triangulating general manifolds","ddc":["510"],"status":"public","file":[{"access_level":"open_access","file_name":"2023_DiscreteCompGeometry_Boissonnat.pdf","content_type":"application/pdf","file_size":582850,"creator":"dernst","relation":"main_file","file_id":"12488","checksum":"46352e0ee71e460848f88685ca852681","success":1,"date_updated":"2023-02-02T11:01:10Z","date_created":"2023-02-02T11:01:10Z"}],"oa_version":"Published Version"},{"type":"journal_article","abstract":[{"lang":"eng","text":"Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift 176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert showed that sets of positive reach in Euclidean space and Riemannian manifolds are very similar. In this paper we introduce a slight variant of Kleinjohann’s and Bangert’s extension and quantify the similarity between sets of positive reach in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we bound the local feature size (a local version of the reach) of its lifting to the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated by the importance of the reach and local feature size to manifold learning, topological inference, and triangulating manifolds and the fact that intrinsic approaches circumvent the curse of dimensionality."}],"title":"The reach of subsets of manifolds","status":"public","intvolume":" 7","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12763","oa_version":"Submitted Version","scopus_import":"1","day":"01","article_processing_charge":"No","article_type":"original","page":"619-641","publication":"Journal of Applied and Computational Topology","citation":{"ama":"Boissonnat JD, Wintraecken M. The reach of subsets of manifolds. Journal of Applied and Computational Topology. 2023;7:619-641. doi:10.1007/s41468-023-00116-x","apa":"Boissonnat, J. D., & Wintraecken, M. (2023). The reach of subsets of manifolds. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-023-00116-x","ieee":"J. D. Boissonnat and M. Wintraecken, “The reach of subsets of manifolds,” Journal of Applied and Computational Topology, vol. 7. Springer Nature, pp. 619–641, 2023.","ista":"Boissonnat JD, Wintraecken M. 2023. The reach of subsets of manifolds. Journal of Applied and Computational Topology. 7, 619–641.","short":"J.D. Boissonnat, M. Wintraecken, Journal of Applied and Computational Topology 7 (2023) 619–641.","mla":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” Journal of Applied and Computational Topology, vol. 7, Springer Nature, 2023, pp. 619–41, doi:10.1007/s41468-023-00116-x.","chicago":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” Journal of Applied and Computational Topology. Springer Nature, 2023. https://doi.org/10.1007/s41468-023-00116-x."},"date_published":"2023-09-01T00:00:00Z","ec_funded":1,"publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Springer Nature","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.","year":"2023","date_updated":"2023-10-04T12:07:18Z","date_created":"2023-03-26T22:01:08Z","volume":7,"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"}],"month":"09","publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"quality_controlled":"1","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"main_file_link":[{"open_access":"1","url":"https://inserm.hal.science/INRIA-SACLAY/hal-04083524v1"}],"oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/s41468-023-00116-x"},{"ec_funded":1,"author":[{"last_name":"Boissonnat","first_name":"Jean Daniel","full_name":"Boissonnat, Jean Daniel"},{"full_name":"Kachanovich, Siargey","last_name":"Kachanovich","first_name":"Siargey"},{"full_name":"Wintraecken, Mathijs","first_name":"Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220"}],"related_material":{"record":[{"id":"9441","relation":"earlier_version","status":"public"}]},"date_updated":"2023-10-10T07:34:35Z","date_created":"2023-05-14T22:01:00Z","volume":52,"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.","year":"2023","publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Society for Industrial and Applied Mathematics","month":"04","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"doi":"10.1137/21M1412918","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://hal-emse.ccsd.cnrs.fr/3IA-COTEDAZUR/hal-04083489v1","open_access":"1"}],"oa":1,"external_id":{"isi":["001013183000012"]},"quality_controlled":"1","isi":1,"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses"}],"abstract":[{"lang":"eng","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. "}],"issue":"2","type":"journal_article","oa_version":"Submitted Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12960","title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations","status":"public","intvolume":" 52","day":"30","article_processing_charge":"No","scopus_import":"1","date_published":"2023-04-30T00:00:00Z","publication":"SIAM Journal on Computing","citation":{"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.” SIAM Journal on Computing, vol. 52, no. 2, Society for Industrial and Applied Mathematics, 2023, pp. 452–86, doi:10.1137/21M1412918.","chicago":"Boissonnat, Jean Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/21M1412918.","ama":"Boissonnat JD, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. 2023;52(2):452-486. doi:10.1137/21M1412918","apa":"Boissonnat, J. D., Kachanovich, S., & Wintraecken, M. (2023). Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1412918","ieee":"J. D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations,” SIAM Journal on Computing, vol. 52, no. 2. Society for Industrial and Applied Mathematics, pp. 452–486, 2023.","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."},"article_type":"original","page":"452-486"},{"date_published":"2022-06-01T00:00:00Z","page":"66:1-66:9","publication":"38th International Symposium on Computational Geometry","citation":{"ama":"Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. A cautionary tale: Burning the medial axis is unstable. In: Goaoc X, Kerber M, eds. 38th International Symposium on Computational Geometry. Vol 224. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:66:1-66:9. doi:10.4230/LIPIcs.SoCG.2022.66","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.","apa":"Chambers, E., Fillmore, C. D., Stephenson, E. R., & Wintraecken, M. (2022). A cautionary tale: Burning the medial axis is unstable. In X. Goaoc & M. Kerber (Eds.), 38th International Symposium on Computational Geometry (Vol. 224, p. 66:1-66:9). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2022.66","ieee":"E. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “A cautionary tale: Burning the medial axis is unstable,” in 38th International Symposium on Computational Geometry, Berlin, Germany, 2022, vol. 224, p. 66:1-66:9.","mla":"Chambers, Erin, et al. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” 38th International Symposium on Computational Geometry, edited by Xavier Goaoc and Michael Kerber, vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 66:1-66:9, doi:10.4230/LIPIcs.SoCG.2022.66.","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.","chicago":"Chambers, Erin, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs Wintraecken. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” In 38th International Symposium on Computational Geometry, edited by Xavier Goaoc and Michael Kerber, 224:66:1-66:9. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SoCG.2022.66."},"day":"01","article_processing_charge":"No","has_accepted_license":"1","series_title":"LIPIcs","scopus_import":"1","oa_version":"Published Version","file":[{"creator":"dernst","file_size":17580705,"content_type":"application/pdf","file_name":"2022_LIPICs_Chambers.pdf","access_level":"open_access","date_updated":"2022-06-07T07:58:30Z","date_created":"2022-06-07T07:58:30Z","success":1,"checksum":"b25ce40fade4ebc0bcaae176db4f5f1f","file_id":"11437","relation":"main_file"}],"ddc":["510"],"title":"A cautionary tale: Burning the medial axis is unstable","status":"public","intvolume":" 224","_id":"11428","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","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"}],"type":"conference","language":[{"iso":"eng"}],"conference":{"end_date":"2022-06-10","start_date":"2022-06-07","location":"Berlin, Germany","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2022.66","quality_controlled":"1","project":[{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"},{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"month":"06","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-227-3"]},"date_updated":"2023-02-21T09:50:52Z","date_created":"2022-06-01T14:18:04Z","volume":224,"author":[{"last_name":"Chambers","first_name":"Erin","full_name":"Chambers, Erin"},{"id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","first_name":"Christopher D","last_name":"Fillmore","full_name":"Fillmore, Christopher D"},{"full_name":"Stephenson, Elizabeth R","first_name":"Elizabeth R","last_name":"Stephenson","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6862-208X"},{"first_name":"Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs"}],"publication_status":"published","editor":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"full_name":"Kerber, Michael","first_name":"Michael","last_name":"Kerber"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"HeEd"}],"year":"2022","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.","file_date_updated":"2022-06-07T07:58:30Z","ec_funded":1},{"date_published":"2022-01-01T00:00:00Z","citation":{"chicago":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL Approximations of Isomanifolds.” Foundations of Computational Mathematics . Springer Nature, 2022. https://doi.org/10.1007/s10208-021-09520-0.","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.” Foundations of Computational Mathematics , vol. 22, Springer Nature, 2022, pp. 967–1012, doi:10.1007/s10208-021-09520-0.","apa":"Boissonnat, J.-D., & Wintraecken, M. (2022). The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . Springer Nature. https://doi.org/10.1007/s10208-021-09520-0","ieee":"J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL approximations of isomanifolds,” Foundations of Computational Mathematics , vol. 22. Springer Nature, pp. 967–1012, 2022.","ista":"Boissonnat J-D, Wintraecken M. 2022. The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . 22, 967–1012.","ama":"Boissonnat J-D, Wintraecken M. The topological correctness of PL approximations of isomanifolds. Foundations of Computational Mathematics . 2022;22:967-1012. doi:10.1007/s10208-021-09520-0"},"publication":"Foundations of Computational Mathematics ","page":"967-1012","article_type":"original","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"01","scopus_import":"1","oa_version":"Published Version","file":[{"creator":"mwintrae","file_size":1455699,"content_type":"application/pdf","file_name":"Boissonnat-Wintraecken2021_Article_TheTopologicalCorrectnessOfPLA.pdf","access_level":"open_access","date_updated":"2021-07-14T06:44:36Z","date_created":"2021-07-14T06:44:36Z","checksum":"f1d372ec3c08ec22e84f8e93e1126b8c","file_id":"9650","relation":"main_file"}],"_id":"9649","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","intvolume":" 22","title":"The topological correctness of PL approximations of isomanifolds","status":"public","ddc":["516"],"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"}],"type":"journal_article","doi":"10.1007/s10208-021-09520-0","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"isi":["000673039600001"]},"oa":1,"project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","isi":1,"publication_identifier":{"eissn":["1615-3383"]},"month":"0","related_material":{"record":[{"id":"7952","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs"}],"volume":22,"date_created":"2021-07-14T06:44:53Z","date_updated":"2023-08-02T06:49:17Z","year":"2022","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.","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"published","ec_funded":1,"file_date_updated":"2021-07-14T06:44:36Z"},{"ec_funded":1,"file_date_updated":"2021-04-22T08:08:14Z","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"full_name":"Heiss, Teresa","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1780-2689","first_name":"Teresa","last_name":"Heiss"},{"full_name":" Kurlin , Vitaliy","last_name":" Kurlin ","first_name":"Vitaliy"},{"last_name":"Smith","first_name":"Philip","full_name":"Smith, Philip"},{"full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"volume":189,"date_created":"2021-04-22T08:09:58Z","date_updated":"2023-02-23T13:55:40Z","year":"2021","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.","department":[{"_id":"HeEd"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","publication_identifier":{"issn":["1868-8969"]},"month":"06","doi":"10.4230/LIPIcs.SoCG.2021.32","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2021-06-11","location":"Virtual","start_date":"2021-06-07"},"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"grant_number":"I4887","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","name":"Discretization in Geometry and Dynamics"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"25C5A090-B435-11E9-9278-68D0E5697425","grant_number":"Z00312"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"quality_controlled":"1","abstract":[{"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.","lang":"eng"}],"type":"conference","alternative_title":["LIPIcs"],"oa_version":"Published Version","file":[{"success":1,"checksum":"1787baef1523d6d93753b90d0c109a6d","date_updated":"2021-04-22T08:08:14Z","date_created":"2021-04-22T08:08:14Z","file_id":"9346","relation":"main_file","creator":"mwintrae","file_size":3117435,"content_type":"application/pdf","access_level":"open_access","file_name":"df_socg_final_version.pdf"}],"_id":"9345","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","intvolume":" 189","title":"The density fingerprint of a periodic point set","ddc":["004","516"],"status":"public","has_accepted_license":"1","article_processing_charge":"No","day":"02","date_published":"2021-06-02T00:00:00Z","citation":{"ama":"Edelsbrunner H, Heiss T, Kurlin V, Smith P, Wintraecken M. The density fingerprint of a periodic point set. In: 37th International Symposium on Computational Geometry (SoCG 2021). Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:32:1-32:16. doi:10.4230/LIPIcs.SoCG.2021.32","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 37th International Symposium on Computational Geometry (SoCG 2021), Virtual, 2021, vol. 189, p. 32:1-32:16.","apa":"Edelsbrunner, H., Heiss, T., Kurlin , V., Smith, P., & Wintraecken, M. (2021). The density fingerprint of a periodic point set. In 37th International Symposium on Computational Geometry (SoCG 2021) (Vol. 189, p. 32:1-32:16). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.32","mla":"Edelsbrunner, Herbert, et al. “The Density Fingerprint of a Periodic Point Set.” 37th International Symposium on Computational Geometry (SoCG 2021), vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16, doi:10.4230/LIPIcs.SoCG.2021.32.","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.","chicago":"Edelsbrunner, Herbert, Teresa Heiss, Vitaliy Kurlin , Philip Smith, and Mathijs Wintraecken. “The Density Fingerprint of a Periodic Point Set.” In 37th International Symposium on Computational Geometry (SoCG 2021), 189:32:1-32:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.32."},"publication":"37th International Symposium on Computational Geometry (SoCG 2021)","page":"32:1-32:16"},{"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"07","doi":"10.1007/s00454-020-00250-8","language":[{"iso":"eng"}],"external_id":{"isi":["000597770300001"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","isi":1,"ec_funded":1,"file_date_updated":"2021-08-06T09:52:29Z","author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"full_name":"Kachanovich, Siargey","first_name":"Siargey","last_name":"Kachanovich"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken","full_name":"Wintraecken, Mathijs"}],"volume":66,"date_updated":"2023-09-05T15:02:40Z","date_created":"2020-12-12T11:07:02Z","year":"2021","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).","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"published","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","day":"01","keyword":["Theoretical Computer Science","Computational Theory and Mathematics","Geometry and Topology","Discrete Mathematics and Combinatorics"],"date_published":"2021-07-01T00:00:00Z","citation":{"chicago":"Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” Discrete & Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00250-8.","mla":"Boissonnat, Jean-Daniel, et al. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” Discrete & Computational Geometry, vol. 66, no. 1, Springer Nature, 2021, pp. 386–434, doi:10.1007/s00454-020-00250-8.","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete & Computational Geometry 66 (2021) 386–434.","ista":"Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete & Computational Geometry. 66(1), 386–434.","apa":"Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00250-8","ieee":"J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Triangulating submanifolds: An elementary and quantified version of Whitney’s method,” Discrete & Computational Geometry, vol. 66, no. 1. Springer Nature, pp. 386–434, 2021.","ama":"Boissonnat J-D, Kachanovich S, Wintraecken M. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete & Computational Geometry. 2021;66(1):386-434. doi:10.1007/s00454-020-00250-8"},"publication":"Discrete & Computational Geometry","page":"386-434","article_type":"original","issue":"1","abstract":[{"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.","lang":"eng"}],"type":"journal_article","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2021_DescreteCompGeopmetry_Boissonnat.pdf","content_type":"application/pdf","file_size":983307,"creator":"kschuh","relation":"main_file","file_id":"9795","checksum":"c848986091e56699dc12de85adb1e39c","success":1,"date_updated":"2021-08-06T09:52:29Z","date_created":"2021-08-06T09:52:29Z"}],"_id":"8940","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":" 66","ddc":["516"],"status":"public","title":"Triangulating submanifolds: An elementary and quantified version of Whitney’s method"},{"publication_identifier":{"isbn":["978-3-95977-184-9"],"issn":["1868-8969"]},"month":"06","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2021.17","conference":{"location":"Virtual","start_date":"2021-06-07","end_date":"2021-06-11","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"place":"Dagstuhl, Germany","ec_funded":1,"file_date_updated":"2021-06-02T10:22:33Z","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.","year":"2021","department":[{"_id":"HeEd"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","related_material":{"record":[{"id":"12960","relation":"later_version","status":"public"}]},"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","first_name":"Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220"}],"volume":189,"date_updated":"2023-10-10T07:34:34Z","date_created":"2021-06-02T10:10:55Z","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","article_processing_charge":"No","has_accepted_license":"1","day":"02","citation":{"ama":"Boissonnat J-D, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In: 37th International Symposium on Computational Geometry (SoCG 2021). Vol 189. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:17:1-17:16. doi:10.4230/LIPIcs.SoCG.2021.17","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.","apa":"Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations. In 37th International Symposium on Computational Geometry (SoCG 2021) (Vol. 189, p. 17:1-17:16). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.17","ieee":"J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations,” in 37th International Symposium on Computational Geometry (SoCG 2021), 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.” 37th International Symposium on Computational Geometry (SoCG 2021), vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 17:1-17:16, doi:10.4230/LIPIcs.SoCG.2021.17.","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.","chicago":"Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter-Freudenthal-Kuhn Triangulations.” In 37th International Symposium on Computational Geometry (SoCG 2021), 189:17:1-17:16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.17."},"publication":"37th International Symposium on Computational Geometry (SoCG 2021)","page":"17:1-17:16","date_published":"2021-06-02T00:00:00Z","type":"conference","alternative_title":["LIPIcs"],"abstract":[{"lang":"eng","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. "}],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","_id":"9441","intvolume":" 189","ddc":["005","516","514"],"title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations","status":"public","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"LIPIcs-SoCG-2021-17.pdf","file_size":1972902,"content_type":"application/pdf","creator":"mwintrae","relation":"main_file","file_id":"9442","checksum":"c322aa48d5d35a35877896cc565705b6","success":1,"date_created":"2021-06-02T10:22:33Z","date_updated":"2021-06-02T10:22:33Z"}]},{"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"09","language":[{"iso":"eng"}],"doi":"10.1007/s00454-020-00233-9","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","isi":1,"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"main_file_link":[{"url":"https://doi.org/10.1007/s00454-020-00233-9","open_access":"1"}],"external_id":{"isi":["000558119300001"]},"ec_funded":1,"volume":66,"date_created":"2020-08-11T07:11:51Z","date_updated":"2024-03-07T14:54:59Z","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"},{"last_name":"Lieutier","first_name":"Andre","full_name":"Lieutier, Andre"},{"orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs"}],"department":[{"_id":"HeEd"}],"publisher":"Springer Nature","publication_status":"published","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.","year":"2021","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","day":"01","scopus_import":"1","date_published":"2021-09-01T00:00:00Z","page":"666-686","article_type":"original","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,” Discrete and Computational Geometry, vol. 66. Springer Nature, pp. 666–686, 2021.","apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., Lieutier, A., & Wintraecken, M. (2021). Local conditions for triangulating submanifolds of Euclidean space. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00233-9","ama":"Boissonnat J-D, Dyer R, Ghosh A, Lieutier A, Wintraecken M. Local conditions for triangulating submanifolds of Euclidean space. Discrete and Computational Geometry. 2021;66:666-686. doi:10.1007/s00454-020-00233-9","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, Andre Lieutier, and Mathijs Wintraecken. “Local Conditions for Triangulating Submanifolds of Euclidean Space.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00233-9.","mla":"Boissonnat, Jean-Daniel, et al. “Local Conditions for Triangulating Submanifolds of Euclidean Space.” Discrete and Computational Geometry, vol. 66, Springer Nature, 2021, pp. 666–86, doi:10.1007/s00454-020-00233-9.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, M. Wintraecken, Discrete and Computational Geometry 66 (2021) 666–686."},"publication":"Discrete and Computational Geometry","abstract":[{"lang":"eng","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."}],"type":"journal_article","oa_version":"Published Version","intvolume":" 66","ddc":["510"],"status":"public","title":"Local conditions for triangulating submanifolds of Euclidean space","_id":"8248","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"month":"03","publication_identifier":{"eissn":["1661-8289"],"issn":["1661-8270"]},"quality_controlled":"1","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"},{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"doi":"10.1007/s11786-020-00461-5","file_date_updated":"2020-11-20T10:18:02Z","ec_funded":1,"publication_status":"published","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"year":"2020","date_updated":"2021-01-12T08:14:13Z","date_created":"2020-03-05T13:30:18Z","volume":14,"author":[{"last_name":"Choudhary","first_name":"Aruni","full_name":"Choudhary, Aruni"},{"full_name":"Kachanovich, Siargey","last_name":"Kachanovich","first_name":"Siargey"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"scopus_import":"1","day":"01","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","article_type":"original","page":"141-176","publication":"Mathematics in Computer Science","citation":{"ista":"Choudhary A, Kachanovich S, Wintraecken M. 2020. Coxeter triangulations have good quality. Mathematics in Computer Science. 14, 141–176.","ieee":"A. Choudhary, S. Kachanovich, and M. Wintraecken, “Coxeter triangulations have good quality,” Mathematics in Computer Science, vol. 14. Springer Nature, pp. 141–176, 2020.","apa":"Choudhary, A., Kachanovich, S., & Wintraecken, M. (2020). Coxeter triangulations have good quality. Mathematics in Computer Science. Springer Nature. https://doi.org/10.1007/s11786-020-00461-5","ama":"Choudhary A, Kachanovich S, Wintraecken M. Coxeter triangulations have good quality. Mathematics in Computer Science. 2020;14:141-176. doi:10.1007/s11786-020-00461-5","chicago":"Choudhary, Aruni, Siargey Kachanovich, and Mathijs Wintraecken. “Coxeter Triangulations Have Good Quality.” Mathematics in Computer Science. Springer Nature, 2020. https://doi.org/10.1007/s11786-020-00461-5.","mla":"Choudhary, Aruni, et al. “Coxeter Triangulations Have Good Quality.” Mathematics in Computer Science, vol. 14, Springer Nature, 2020, pp. 141–76, doi:10.1007/s11786-020-00461-5.","short":"A. Choudhary, S. Kachanovich, M. Wintraecken, Mathematics in Computer Science 14 (2020) 141–176."},"date_published":"2020-03-01T00:00:00Z","type":"journal_article","abstract":[{"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.","lang":"eng"}],"title":"Coxeter triangulations have good quality","ddc":["510"],"status":"public","intvolume":" 14","_id":"7567","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_created":"2020-11-20T10:18:02Z","date_updated":"2020-11-20T10:18:02Z","checksum":"1d145f3ab50ccee735983cb89236e609","success":1,"relation":"main_file","file_id":"8783","file_size":872275,"content_type":"application/pdf","creator":"dernst","file_name":"2020_MathCompScie_Choudhary.pdf","access_level":"open_access"}],"oa_version":"Published Version"},{"intvolume":" 164","title":"The topological correctness of PL-approximations of isomanifolds","ddc":["510"],"status":"public","_id":"7952","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_name":"2020_LIPIcsSoCG_Boissonnat.pdf","access_level":"open_access","creator":"dernst","file_size":1009739,"content_type":"application/pdf","file_id":"7969","relation":"main_file","date_created":"2020-06-17T10:13:34Z","date_updated":"2020-07-14T12:48:06Z","checksum":"38cbfa4f5d484d267a35d44d210df044"}],"oa_version":"Published Version","alternative_title":["LIPIcs"],"type":"conference","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. "}],"citation":{"chicago":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.20.","short":"J.-D. Boissonnat, M. Wintraecken, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” 36th International Symposium on Computational Geometry, vol. 164, 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.20.","apa":"Boissonnat, J.-D., & Wintraecken, M. (2020). The topological correctness of PL-approximations of isomanifolds. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.20","ieee":"J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL-approximations of isomanifolds,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","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.","ama":"Boissonnat J-D, Wintraecken M. The topological correctness of PL-approximations of isomanifolds. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.20"},"publication":"36th International Symposium on Computational Geometry","date_published":"2020-06-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"01","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"HeEd"}],"publication_status":"published","year":"2020","volume":164,"date_updated":"2023-08-02T06:49:16Z","date_created":"2020-06-09T07:24:11Z","related_material":{"record":[{"id":"9649","relation":"later_version","status":"public"}]},"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"}],"article_number":"20:1-20:18","ec_funded":1,"file_date_updated":"2020-07-14T12:48:06Z","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.20","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","start_date":"2020-06-22","location":"Zürich, Switzerland"},"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-143-6"]},"month":"06"},{"date_updated":"2023-10-10T13:05:27Z","date_created":"2020-07-24T07:09:18Z","volume":57,"author":[{"full_name":"Vegter, Gert","last_name":"Vegter","first_name":"Gert"},{"last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Akadémiai Kiadó","year":"2020","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.","file_date_updated":"2020-07-24T07:09:06Z","ec_funded":1,"language":[{"iso":"eng"}],"doi":"10.1556/012.2020.57.2.1454","isi":1,"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","call_identifier":"FWF"}],"oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)"},"external_id":{"isi":["000570978400005"]},"month":"07","publication_identifier":{"eissn":["1588-2896"],"issn":["0081-6906"]},"oa_version":"Published Version","file":[{"file_size":1476072,"content_type":"application/pdf","creator":"mwintrae","file_name":"57-2-05_4214-1454Vegter-Wintraecken_OpenAccess_CC-BY-NC.pdf","access_level":"open_access","date_created":"2020-07-24T07:09:06Z","date_updated":"2020-07-24T07:09:06Z","relation":"main_file","file_id":"8164"}],"status":"public","ddc":["510"],"title":"Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes","intvolume":" 57","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"8163","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"}],"issue":"2","type":"journal_article","date_published":"2020-07-24T00:00:00Z","article_type":"original","page":"193-199","publication":"Studia Scientiarum Mathematicarum Hungarica","citation":{"apa":"Vegter, G., & Wintraecken, M. (2020). Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. Akadémiai Kiadó. https://doi.org/10.1556/012.2020.57.2.1454","ieee":"G. Vegter and M. Wintraecken, “Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes,” Studia Scientiarum Mathematicarum Hungarica, vol. 57, no. 2. Akadémiai Kiadó, pp. 193–199, 2020.","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.","ama":"Vegter G, Wintraecken M. Refutation of a claim made by Fejes Tóth on the accuracy of surface meshes. Studia Scientiarum Mathematicarum Hungarica. 2020;57(2):193-199. doi:10.1556/012.2020.57.2.1454","chicago":"Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum Hungarica. Akadémiai Kiadó, 2020. https://doi.org/10.1556/012.2020.57.2.1454.","short":"G. Vegter, M. Wintraecken, Studia Scientiarum Mathematicarum Hungarica 57 (2020) 193–199.","mla":"Vegter, Gert, and Mathijs Wintraecken. “Refutation of a Claim Made by Fejes Tóth on the Accuracy of Surface Meshes.” Studia Scientiarum Mathematicarum Hungarica, vol. 57, no. 2, Akadémiai Kiadó, 2020, pp. 193–99, doi:10.1556/012.2020.57.2.1454."},"day":"24","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1"},{"month":"07","publication_identifier":{"issn":["1920-180X"]},"doi":"10.20382/jocg.v10i1a9","language":[{"iso":"eng"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"file_date_updated":"2020-07-14T12:47:32Z","ec_funded":1,"author":[{"full_name":"Dyer, Ramsay","last_name":"Dyer","first_name":"Ramsay"},{"full_name":"Vegter, Gert","last_name":"Vegter","first_name":"Gert"},{"full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2019-06-03T09:35:33Z","date_updated":"2021-01-12T08:07:50Z","volume":10,"year":"2019","publication_status":"published","publisher":"Carleton University","department":[{"_id":"HeEd"}],"day":"01","has_accepted_license":"1","scopus_import":1,"date_published":"2019-07-01T00:00:00Z","publication":"Journal of Computational Geometry ","citation":{"mla":"Dyer, Ramsay, et al. “Simplices Modelled on Spaces of Constant Curvature.” Journal of Computational Geometry , vol. 10, no. 1, Carleton University, 2019, pp. 223–256, doi:10.20382/jocg.v10i1a9.","short":"R. Dyer, G. Vegter, M. Wintraecken, Journal of Computational Geometry 10 (2019) 223–256.","chicago":"Dyer, Ramsay, Gert Vegter, and Mathijs Wintraecken. “Simplices Modelled on Spaces of Constant Curvature.” Journal of Computational Geometry . Carleton University, 2019. https://doi.org/10.20382/jocg.v10i1a9.","ama":"Dyer R, Vegter G, Wintraecken M. Simplices modelled on spaces of constant curvature. Journal of Computational Geometry . 2019;10(1):223–256. doi:10.20382/jocg.v10i1a9","ista":"Dyer R, Vegter G, Wintraecken M. 2019. Simplices modelled on spaces of constant curvature. Journal of Computational Geometry . 10(1), 223–256.","ieee":"R. Dyer, G. Vegter, and M. Wintraecken, “Simplices modelled on spaces of constant curvature,” Journal of Computational Geometry , vol. 10, no. 1. Carleton University, pp. 223–256, 2019.","apa":"Dyer, R., Vegter, G., & Wintraecken, M. (2019). Simplices modelled on spaces of constant curvature. Journal of Computational Geometry . Carleton University. https://doi.org/10.20382/jocg.v10i1a9"},"page":"223–256","abstract":[{"lang":"eng","text":"We give non-degeneracy criteria for Riemannian simplices based on simplices in spaces of constant sectional curvature. It extends previous work on Riemannian simplices, where we developed Riemannian simplices with respect to Euclidean reference simplices. The criteria we give in this article are in terms of quality measures for spaces of constant curvature that we develop here. We see that simplices in spaces that have nearly constant curvature, are already non-degenerate under very weak quality demands. This is of importance because it allows for sampling of Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature."}],"issue":"1","type":"journal_article","oa_version":"Published Version","file":[{"file_id":"6516","relation":"main_file","date_created":"2019-06-03T09:30:01Z","date_updated":"2020-07-14T12:47:32Z","checksum":"57b4df2f16a74eb499734ec8ee240178","file_name":"mainJournalFinal.pdf","access_level":"open_access","creator":"mwintrae","content_type":"application/pdf","file_size":2170882}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"6515","ddc":["510"],"title":"Simplices modelled on spaces of constant curvature","status":"public","intvolume":" 10"},{"language":[{"iso":"eng"}],"conference":{"start_date":"2019-08-08","location":"Edmonton, Canada","end_date":"2019-08-10","name":"CCCG: Canadian Conference in Computational Geometry"},"date_published":"2019-08-01T00:00:00Z","quality_controlled":"1","page":"275-279","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"publication":"The 31st Canadian Conference in Computational Geometry","citation":{"apa":"Vegter, G., & Wintraecken, M. (2019). The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds. In The 31st Canadian Conference in Computational Geometry (pp. 275–279). Edmonton, Canada.","ieee":"G. Vegter and M. Wintraecken, “The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds,” in The 31st Canadian Conference in Computational Geometry, Edmonton, Canada, 2019, pp. 275–279.","ista":"Vegter G, Wintraecken M. 2019. The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds. The 31st Canadian Conference in Computational Geometry. CCCG: Canadian Conference in Computational Geometry, 275–279.","ama":"Vegter G, Wintraecken M. The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds. In: The 31st Canadian Conference in Computational Geometry. ; 2019:275-279.","chicago":"Vegter, Gert, and Mathijs Wintraecken. “The Extrinsic Nature of the Hausdorff Distance of Optimal Triangulations of Manifolds.” In The 31st Canadian Conference in Computational Geometry, 275–79, 2019.","short":"G. Vegter, M. Wintraecken, in:, The 31st Canadian Conference in Computational Geometry, 2019, pp. 275–279.","mla":"Vegter, Gert, and Mathijs Wintraecken. “The Extrinsic Nature of the Hausdorff Distance of Optimal Triangulations of Manifolds.” The 31st Canadian Conference in Computational Geometry, 2019, pp. 275–79."},"oa":1,"month":"08","day":"01","has_accepted_license":"1","scopus_import":1,"date_created":"2019-07-12T08:34:57Z","date_updated":"2021-01-12T08:08:16Z","oa_version":"Submitted Version","file":[{"creator":"mwintrae","content_type":"application/pdf","file_size":321176,"access_level":"open_access","file_name":"IntrinsicExtrinsicCCCG2019.pdf","checksum":"ceabd152cfa55170d57763f9c6c60a53","date_updated":"2020-07-14T12:47:34Z","date_created":"2019-07-12T08:32:46Z","file_id":"6629","relation":"main_file"}],"author":[{"full_name":"Vegter, Gert","first_name":"Gert","last_name":"Vegter"},{"orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs"}],"title":"The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds","ddc":["004"],"publication_status":"published","status":"public","department":[{"_id":"HeEd"}],"_id":"6628","year":"2019","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:34Z","abstract":[{"text":"Fejes Tóth [5] and Schneider [9] studied approximations of smooth convex hypersurfaces in Euclidean space by piecewise flat triangular meshes with a given number of vertices on the hypersurface that are optimal with respect to Hausdorff distance. They proved that this Hausdorff distance decreases inversely proportional with m 2/(d−1), where m is the number of vertices and d is the dimension of Euclidean space. Moreover the pro-portionality constant can be expressed in terms of the Gaussian curvature, an intrinsic quantity. In this short note, we prove the extrinsic nature of this constant for manifolds of sufficiently high codimension. We do so by constructing an family of isometric embeddings of the flat torus in Euclidean space.","lang":"eng"}],"ec_funded":1,"type":"conference"},{"type":"journal_article","extern":"1","issue":"3","abstract":[{"text":"The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\\mathbb{R}^2$ and on surfaces embedded in $\\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\\mathcal{P}$ in a domain $\\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened.","lang":"eng"}],"intvolume":" 48","publisher":"Society for Industrial & Applied Mathematics (SIAM)","status":"public","publication_status":"published","title":"Anisotropic triangulations via discrete Riemannian Voronoi diagrams","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6672","year":"2019","oa_version":"Preprint","volume":48,"date_created":"2019-07-24T08:42:12Z","date_updated":"2021-01-12T08:08:30Z","author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"last_name":"Rouxel-Labbé","first_name":"Mael","full_name":"Rouxel-Labbé, Mael"},{"orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs"}],"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"05","day":"21","page":"1046-1097","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1703.06487"}],"external_id":{"arxiv":["1703.06487"]},"citation":{"short":"J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097.","mla":"Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing, vol. 48, no. 3, Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:10.1137/17m1152292.","chicago":"Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2019. https://doi.org/10.1137/17m1152292.","ama":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 2019;48(3):1046-1097. doi:10.1137/17m1152292","apa":"Boissonnat, J.-D., Rouxel-Labbé, M., & Wintraecken, M. (2019). Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/17m1152292","ieee":"J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations via discrete Riemannian Voronoi diagrams,” SIAM Journal on Computing, vol. 48, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1046–1097, 2019.","ista":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. 2019. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097."},"oa":1,"publication":"SIAM Journal on Computing","language":[{"iso":"eng"}],"date_published":"2019-05-21T00:00:00Z","doi":"10.1137/17m1152292"},{"type":"journal_article","abstract":[{"lang":"eng","text":"In this paper we discuss three results. The first two concern general sets of positive reach: we first characterize the reach of a closed set by means of a bound on the metric distortion between the distance measured in the ambient Euclidean space and the shortest path distance measured in the set. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the reach and the distance between the two points."}],"issue":"1-2","_id":"6671","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"title":"The reach, metric distortion, geodesic convexity and the variation of tangent spaces","status":"public","intvolume":" 3","file":[{"file_id":"6741","relation":"main_file","date_updated":"2020-07-14T12:47:36Z","date_created":"2019-07-31T08:09:56Z","checksum":"a5b244db9f751221409cf09c97ee0935","file_name":"2019_JournAppliedComputTopol_Boissonnat.pdf","access_level":"open_access","creator":"dernst","file_size":2215157,"content_type":"application/pdf"}],"oa_version":"Published Version","day":"01","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","publication":"Journal of Applied and Computational Topology","citation":{"mla":"Boissonnat, Jean-Daniel, et al. “The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces.” Journal of Applied and Computational Topology, vol. 3, no. 1–2, Springer Nature, 2019, pp. 29–58, doi:10.1007/s41468-019-00029-8.","short":"J.-D. Boissonnat, A. Lieutier, M. Wintraecken, Journal of Applied and Computational Topology 3 (2019) 29–58.","chicago":"Boissonnat, Jean-Daniel, André Lieutier, and Mathijs Wintraecken. “The Reach, Metric Distortion, Geodesic Convexity and the Variation of Tangent Spaces.” Journal of Applied and Computational Topology. Springer Nature, 2019. https://doi.org/10.1007/s41468-019-00029-8.","ama":"Boissonnat J-D, Lieutier A, Wintraecken M. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. 2019;3(1-2):29–58. doi:10.1007/s41468-019-00029-8","ista":"Boissonnat J-D, Lieutier A, Wintraecken M. 2019. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. 3(1–2), 29–58.","ieee":"J.-D. Boissonnat, A. Lieutier, and M. Wintraecken, “The reach, metric distortion, geodesic convexity and the variation of tangent spaces,” Journal of Applied and Computational Topology, vol. 3, no. 1–2. Springer Nature, pp. 29–58, 2019.","apa":"Boissonnat, J.-D., Lieutier, A., & Wintraecken, M. (2019). The reach, metric distortion, geodesic convexity and the variation of tangent spaces. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-019-00029-8"},"article_type":"original","page":"29–58","date_published":"2019-06-01T00:00:00Z","file_date_updated":"2020-07-14T12:47:36Z","ec_funded":1,"year":"2019","publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Springer Nature","author":[{"last_name":"Boissonnat","first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel"},{"first_name":"André","last_name":"Lieutier","full_name":"Lieutier, André"},{"last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"date_created":"2019-07-24T08:37:29Z","date_updated":"2023-08-22T12:37:47Z","volume":3,"month":"06","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"doi":"10.1007/s41468-019-00029-8","language":[{"iso":"eng"}]},{"article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2017-01-01T00:00:00Z","citation":{"mla":"Pranav, Pratyush, et al. “The Topology of the Cosmic Web in Terms of Persistent Betti Numbers.” Monthly Notices of the Royal Astronomical Society, vol. 465, no. 4, Oxford University Press, 2017, pp. 4281–310, doi:10.1093/mnras/stw2862.","short":"P. Pranav, H. Edelsbrunner, R. Van De Weygaert, G. Vegter, M. Kerber, B. Jones, M. Wintraecken, Monthly Notices of the Royal Astronomical Society 465 (2017) 4281–4310.","chicago":"Pranav, Pratyush, Herbert Edelsbrunner, Rien Van De Weygaert, Gert Vegter, Michael Kerber, Bernard Jones, and Mathijs Wintraecken. “The Topology of the Cosmic Web in Terms of Persistent Betti Numbers.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2017. https://doi.org/10.1093/mnras/stw2862.","ama":"Pranav P, Edelsbrunner H, Van De Weygaert R, et al. The topology of the cosmic web in terms of persistent Betti numbers. Monthly Notices of the Royal Astronomical Society. 2017;465(4):4281-4310. doi:10.1093/mnras/stw2862","ista":"Pranav P, Edelsbrunner H, Van De Weygaert R, Vegter G, Kerber M, Jones B, Wintraecken M. 2017. The topology of the cosmic web in terms of persistent Betti numbers. Monthly Notices of the Royal Astronomical Society. 465(4), 4281–4310.","ieee":"P. Pranav et al., “The topology of the cosmic web in terms of persistent Betti numbers,” Monthly Notices of the Royal Astronomical Society, vol. 465, no. 4. Oxford University Press, pp. 4281–4310, 2017.","apa":"Pranav, P., Edelsbrunner, H., Van De Weygaert, R., Vegter, G., Kerber, M., Jones, B., & Wintraecken, M. (2017). The topology of the cosmic web in terms of persistent Betti numbers. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stw2862"},"publication":"Monthly Notices of the Royal Astronomical Society","page":"4281 - 4310","issue":"4","abstract":[{"lang":"eng","text":"We introduce a multiscale topological description of the Megaparsec web-like cosmic matter distribution. Betti numbers and topological persistence offer a powerful means of describing the rich connectivity structure of the cosmic web and of its multiscale arrangement of matter and galaxies. Emanating from algebraic topology and Morse theory, Betti numbers and persistence diagrams represent an extension and deepening of the cosmologically familiar topological genus measure and the related geometric Minkowski functionals. In addition to a description of the mathematical background, this study presents the computational procedure for computing Betti numbers and persistence diagrams for density field filtrations. The field may be computed starting from a discrete spatial distribution of galaxies or simulation particles. The main emphasis of this study concerns an extensive and systematic exploration of the imprint of different web-like morphologies and different levels of multiscale clustering in the corresponding computed Betti numbers and persistence diagrams. To this end, we use Voronoi clustering models as templates for a rich variety of web-like configurations and the fractal-like Soneira-Peebles models exemplify a range of multiscale configurations. We have identified the clear imprint of cluster nodes, filaments, walls, and voids in persistence diagrams, along with that of the nested hierarchy of structures in multiscale point distributions. We conclude by outlining the potential of persistent topology for understanding the connectivity structure of the cosmic web, in large simulations of cosmic structure formation and in the challenging context of the observed galaxy distribution in large galaxy surveys."}],"type":"journal_article","oa_version":"Submitted Version","_id":"1022","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":" 465","title":"The topology of the cosmic web in terms of persistent Betti numbers","status":"public","publication_identifier":{"issn":["00358711"]},"month":"01","doi":"10.1093/mnras/stw2862","language":[{"iso":"eng"}],"oa":1,"external_id":{"isi":["000395170200039"]},"main_file_link":[{"url":"https://arxiv.org/abs/1608.04519","open_access":"1"}],"quality_controlled":"1","isi":1,"publist_id":"6373","author":[{"full_name":"Pranav, Pratyush","first_name":"Pratyush","last_name":"Pranav"},{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"last_name":"Van De Weygaert","first_name":"Rien","full_name":"Van De Weygaert, Rien"},{"first_name":"Gert","last_name":"Vegter","full_name":"Vegter, Gert"},{"full_name":"Kerber, Michael","last_name":"Kerber","first_name":"Michael"},{"first_name":"Bernard","last_name":"Jones","full_name":"Jones, Bernard"},{"first_name":"Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs"}],"volume":465,"date_created":"2018-12-11T11:49:44Z","date_updated":"2023-09-22T09:40:55Z","acknowledgement":"Part of this work has been supported by the 7th Framework Programme for Research of the European Commission, under FETOpen grant number 255827 (CGL Computational Geometry Learning) and ERC advanced grant, URSAT (Understanding Random Systems via Algebraic Topology) number 320422.","year":"2017","publisher":"Oxford University Press","department":[{"_id":"HeEd"}],"publication_status":"published"}]