[{"doi":"10.1007/s00454-020-00250-8","date_published":"2021-07-01T00:00:00Z","date_created":"2020-12-12T11:07:02Z","page":"386-434","day":"01","publication":"Discrete & Computational Geometry","has_accepted_license":"1","isi":1,"year":"2021","quality_controlled":"1","publisher":"Springer Nature","oa":1,"acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement Number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). 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).","title":"Triangulating submanifolds: An elementary and quantified version of Whitney’s method","author":[{"first_name":"Jean-Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean-Daniel"},{"first_name":"Siargey","last_name":"Kachanovich","full_name":"Kachanovich, Siargey"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs"}],"external_id":{"isi":["000597770300001"]},"article_processing_charge":"Yes (via OA deal)","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","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.","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","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.","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete & Computational Geometry 66 (2021) 386–434.","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."},"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"volume":66,"issue":"1","ec_funded":1,"file":[{"date_updated":"2021-08-06T09:52:29Z","file_size":983307,"creator":"kschuh","date_created":"2021-08-06T09:52:29Z","file_name":"2021_DescreteCompGeopmetry_Boissonnat.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"9795","checksum":"c848986091e56699dc12de85adb1e39c","success":1}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publication_status":"published","month":"07","intvolume":" 66","oa_version":"Published Version","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."}],"file_date_updated":"2021-08-06T09:52:29Z","department":[{"_id":"HeEd"}],"ddc":["516"],"date_updated":"2023-09-05T15:02:40Z","status":"public","keyword":["Theoretical Computer Science","Computational Theory and Mathematics","Geometry and Topology","Discrete Mathematics and Combinatorics"],"article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"8940"},{"intvolume":" 5","month":"03","scopus_import":"1","oa_version":"Published Version","abstract":[{"text":"We study the probabilistic convergence between the mapper graph and the Reeb graph of a topological space X equipped with a continuous function f:X→R. We first give a categorification of the mapper graph and the Reeb graph by interpreting them in terms of cosheaves and stratified covers of the real line R. We then introduce a variant of the classic mapper graph of Singh et al. (in: Eurographics symposium on point-based graphics, 2007), referred to as the enhanced mapper graph, and demonstrate that such a construction approximates the Reeb graph of (X,f) when it is applied to points randomly sampled from a probability density function concentrated on (X,f). Our techniques are based on the interleaving distance of constructible cosheaves and topological estimation via kernel density estimates. Following Munch and Wang (In: 32nd international symposium on computational geometry, volume 51 of Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, Germany, pp 53:1–53:16, 2016), we first show that the mapper graph of (X,f), a constructible R-space (with a fixed open cover), approximates the Reeb graph of the same space. We then construct an isomorphism between the mapper of (X,f) to the mapper of a super-level set of a probability density function concentrated on (X,f). Finally, building on the approach of Bobrowski et al. (Bernoulli 23(1):288–328, 2017b), we show that, with high probability, we can recover the mapper of the super-level set given a sufficiently large sample. Our work is the first to consider the mapper construction using the theory of cosheaves in a probabilistic setting. It is part of an ongoing effort to combine sheaf theory, probability, and statistics, to support topological data analysis with random data.","lang":"eng"}],"ec_funded":1,"volume":5,"issue":"1","language":[{"iso":"eng"}],"file":[{"file_id":"9112","checksum":"3f02e9d47c428484733da0f588a3c069","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2021-02-11T14:43:59Z","file_name":"2020_JourApplCompTopology_Brown.pdf","creator":"dernst","date_updated":"2021-02-11T14:43:59Z","file_size":2090265}],"publication_status":"published","publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","_id":"9111","department":[{"_id":"HeEd"}],"file_date_updated":"2021-02-11T14:43:59Z","ddc":["510"],"date_updated":"2023-09-05T15:37:56Z","oa":1,"quality_controlled":"1","publisher":"Springer Nature","acknowledgement":"AB was supported in part by the European Union’s Horizon 2020 research and innovation\r\nprogramme under the Marie Sklodowska-Curie GrantAgreement No. 754411 and NSF IIS-1513616. OB was supported in part by the Israel Science Foundation, Grant 1965/19. BW was supported in part by NSF IIS-1513616 and DBI-1661375. EM was supported in part by NSF CMMI-1800466, DMS-1800446, and CCF-1907591.We would like to thank the Institute for Mathematics and its Applications for hosting a workshop titled Bridging Statistics and Sheaves in May 2018, where this work was conceived.\r\nOpen Access funding provided by Institute of Science and Technology (IST Austria).","date_created":"2021-02-11T14:41:02Z","doi":"10.1007/s41468-020-00063-x","date_published":"2021-03-01T00:00:00Z","page":"99-140","publication":"Journal of Applied and Computational Topology","day":"01","year":"2021","has_accepted_license":"1","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"title":"Probabilistic convergence and stability of random mapper graphs","external_id":{"arxiv":["1909.03488"]},"article_processing_charge":"Yes (via OA deal)","author":[{"full_name":"Brown, Adam","last_name":"Brown","id":"70B7FDF6-608D-11E9-9333-8535E6697425","first_name":"Adam"},{"first_name":"Omer","full_name":"Bobrowski, Omer","last_name":"Bobrowski"},{"first_name":"Elizabeth","full_name":"Munch, Elizabeth","last_name":"Munch"},{"first_name":"Bei","full_name":"Wang, Bei","last_name":"Wang"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Brown, Adam, Omer Bobrowski, Elizabeth Munch, and Bei Wang. “Probabilistic Convergence and Stability of Random Mapper Graphs.” Journal of Applied and Computational Topology. Springer Nature, 2021. https://doi.org/10.1007/s41468-020-00063-x.","ista":"Brown A, Bobrowski O, Munch E, Wang B. 2021. Probabilistic convergence and stability of random mapper graphs. Journal of Applied and Computational Topology. 5(1), 99–140.","mla":"Brown, Adam, et al. “Probabilistic Convergence and Stability of Random Mapper Graphs.” Journal of Applied and Computational Topology, vol. 5, no. 1, Springer Nature, 2021, pp. 99–140, doi:10.1007/s41468-020-00063-x.","ama":"Brown A, Bobrowski O, Munch E, Wang B. Probabilistic convergence and stability of random mapper graphs. Journal of Applied and Computational Topology. 2021;5(1):99-140. doi:10.1007/s41468-020-00063-x","apa":"Brown, A., Bobrowski, O., Munch, E., & Wang, B. (2021). Probabilistic convergence and stability of random mapper graphs. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-020-00063-x","short":"A. Brown, O. Bobrowski, E. Munch, B. Wang, Journal of Applied and Computational Topology 5 (2021) 99–140.","ieee":"A. Brown, O. Bobrowski, E. Munch, and B. Wang, “Probabilistic convergence and stability of random mapper graphs,” Journal of Applied and Computational Topology, vol. 5, no. 1. Springer Nature, pp. 99–140, 2021."}},{"oa":1,"publisher":"Institute of Science and Technology Austria","date_created":"2021-02-02T14:11:06Z","doi":"10.15479/AT:ISTA:9056","date_published":"2021-02-01T00:00:00Z","page":"134","day":"01","year":"2021","has_accepted_license":"1","title":"Multi-cover persistence and Delaunay mosaics","article_processing_charge":"No","author":[{"first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","last_name":"Osang"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Osang GF. 2021. Multi-cover persistence and Delaunay mosaics. Klosterneuburg: Institute of Science and Technology Austria.","chicago":"Osang, Georg F. “Multi-Cover Persistence and Delaunay Mosaics.” Institute of Science and Technology Austria, 2021. https://doi.org/10.15479/AT:ISTA:9056.","ama":"Osang GF. Multi-cover persistence and Delaunay mosaics. 2021. doi:10.15479/AT:ISTA:9056","apa":"Osang, G. F. (2021). Multi-cover persistence and Delaunay mosaics. Institute of Science and Technology Austria, Klosterneuburg. https://doi.org/10.15479/AT:ISTA:9056","ieee":"G. F. Osang, “Multi-cover persistence and Delaunay mosaics,” Institute of Science and Technology Austria, Klosterneuburg, 2021.","short":"G.F. Osang, Multi-Cover Persistence and Delaunay Mosaics, Institute of Science and Technology Austria, 2021.","mla":"Osang, Georg F. Multi-Cover Persistence and Delaunay Mosaics. Institute of Science and Technology Austria, 2021, doi:10.15479/AT:ISTA:9056."},"place":"Klosterneuburg","month":"02","alternative_title":["ISTA Thesis"],"oa_version":"Published Version","abstract":[{"text":"In this thesis we study persistence of multi-covers of Euclidean balls and the geometric structures underlying their computation, in particular Delaunay mosaics and Voronoi tessellations. The k-fold cover for some discrete input point set consists of the space where at least k balls of radius r around the input points overlap. Persistence is a notion that captures, in some sense, the topology of the shape underlying the input. While persistence is usually computed for the union of balls, the k-fold cover is of interest as it captures local density,\r\nand thus might approximate the shape of the input better if the input data is noisy. To compute persistence of these k-fold covers, we need a discretization that is provided by higher-order Delaunay mosaics. We present and implement a simple and efficient algorithm for the computation of higher-order Delaunay mosaics, and use it to give experimental results for their combinatorial properties. The algorithm makes use of a new geometric structure, the rhomboid tiling. It contains the higher-order Delaunay mosaics as slices, and by introducing a filtration\r\nfunction on the tiling, we also obtain higher-order α-shapes as slices. These allow us to compute persistence of the multi-covers for varying radius r; the computation for varying k is less straight-foward and involves the rhomboid tiling directly. We apply our algorithms to experimental sphere packings to shed light on their structural properties. Finally, inspired by periodic structures in packings and materials, we propose and implement an algorithm for periodic Delaunay triangulations to be integrated into the Computational Geometry Algorithms Library (CGAL), and discuss the implications on persistence for periodic data sets.","lang":"eng"}],"related_material":{"record":[{"status":"public","id":"187","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"8703"}]},"language":[{"iso":"eng"}],"file":[{"access_level":"closed","relation":"source_file","content_type":"application/zip","checksum":"bcf27986147cab0533b6abadd74e7629","file_id":"9063","creator":"patrickd","date_updated":"2021-02-03T10:37:28Z","file_size":13446994,"date_created":"2021-02-02T14:09:25Z","file_name":"thesis_source.zip"},{"success":1,"file_id":"9064","checksum":"9cc8af266579a464385bbe2aff6af606","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"thesis_pdfA2b.pdf","date_created":"2021-02-02T14:09:18Z","creator":"patrickd","file_size":5210329,"date_updated":"2021-02-02T14:09:18Z"}],"degree_awarded":"PhD","publication_status":"published","publication_identifier":{"issn":["2663-337X"]},"status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"dissertation","_id":"9056","file_date_updated":"2021-02-03T10:37:28Z","department":[{"_id":"HeEd"},{"_id":"GradSch"}],"ddc":["006","514","516"],"date_updated":"2023-09-07T13:29:01Z","supervisor":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"}]},{"title":"Topological signatures and stability of hexagonal close packing and Barlow stackings","author":[{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","first_name":"Georg F","last_name":"Osang","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116"},{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"full_name":"Saadatfar, Mohammad","last_name":"Saadatfar","first_name":"Mohammad"}],"article_processing_charge":"No","external_id":{"pmid":["34569592"],"isi":["000700090000001"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Osang GF, Edelsbrunner H, Saadatfar M. 2021. Topological signatures and stability of hexagonal close packing and Barlow stackings. Soft Matter. 17(40), 9107–9115.","chicago":"Osang, Georg F, Herbert Edelsbrunner, and Mohammad Saadatfar. “Topological Signatures and Stability of Hexagonal Close Packing and Barlow Stackings.” Soft Matter. Royal Society of Chemistry , 2021. https://doi.org/10.1039/d1sm00774b.","short":"G.F. Osang, H. Edelsbrunner, M. Saadatfar, Soft Matter 17 (2021) 9107–9115.","ieee":"G. F. Osang, H. Edelsbrunner, and M. Saadatfar, “Topological signatures and stability of hexagonal close packing and Barlow stackings,” Soft Matter, vol. 17, no. 40. Royal Society of Chemistry , pp. 9107–9115, 2021.","apa":"Osang, G. F., Edelsbrunner, H., & Saadatfar, M. (2021). Topological signatures and stability of hexagonal close packing and Barlow stackings. Soft Matter. Royal Society of Chemistry . https://doi.org/10.1039/d1sm00774b","ama":"Osang GF, Edelsbrunner H, Saadatfar M. Topological signatures and stability of hexagonal close packing and Barlow stackings. Soft Matter. 2021;17(40):9107-9115. doi:10.1039/d1sm00774b","mla":"Osang, Georg F., et al. “Topological Signatures and Stability of Hexagonal Close Packing and Barlow Stackings.” Soft Matter, vol. 17, no. 40, Royal Society of Chemistry , 2021, pp. 9107–15, doi:10.1039/d1sm00774b."},"project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"date_published":"2021-10-20T00:00:00Z","doi":"10.1039/d1sm00774b","date_created":"2021-10-31T23:01:30Z","page":"9107-9115","day":"20","publication":"Soft Matter","isi":1,"has_accepted_license":"1","year":"2021","publisher":"Royal Society of Chemistry ","quality_controlled":"1","oa":1,"acknowledgement":"MS acknowledges the support by Australian Research Council funding through the ARC Training Centre for M3D Innovation (IC180100008). MS thanks M. Hanifpour and N. Francois for their input and valuable discussions. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme, grant no. 788183 and from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","file_date_updated":"2023-10-03T09:21:42Z","department":[{"_id":"HeEd"}],"ddc":["540"],"date_updated":"2023-10-03T09:24:27Z","status":"public","type":"journal_article","article_type":"original","_id":"10204","issue":"40","volume":17,"ec_funded":1,"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"b4da0c420530295e61b153960f6cb350","file_id":"14385","success":1,"creator":"dernst","date_updated":"2023-10-03T09:21:42Z","file_size":4678788,"date_created":"2023-10-03T09:21:42Z","file_name":"2021_SoftMatter_acceptedversion_Osang.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1744-6848"],"issn":["1744-683X"]},"publication_status":"published","month":"10","intvolume":" 17","scopus_import":"1","oa_version":"Submitted Version","pmid":1,"abstract":[{"lang":"eng","text":"Two common representations of close packings of identical spheres consisting of hexagonal layers, called Barlow stackings, appear abundantly in minerals and metals. These motifs, however, occupy an identical portion of space and bear identical first-order topological signatures as measured by persistent homology. Here we present a novel method based on k-fold covers that unambiguously distinguishes between these patterns. Moreover, our approach provides topological evidence that the FCC motif is the more stable of the two in the context of evolving experimental sphere packings during the transition from disordered to an ordered state. We conclude that our approach can be generalised to distinguish between various Barlow stackings manifested in minerals and metals."}]},{"publication_identifier":{"issn":["18688969"],"isbn":["9783959771849"]},"publication_status":"published","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"0de217501e7ba8b267d58deed0d51761","file_id":"9610","success":1,"creator":"cziletti","date_updated":"2021-06-28T12:40:47Z","file_size":"1367983","date_created":"2021-06-28T12:40:47Z","file_name":"2021_LIPIcs_Corbet.pdf"}],"language":[{"iso":"eng"}],"related_material":{"link":[{"relation":"extended_version","url":"https://arxiv.org/abs/2103.07823"}],"record":[{"relation":"later_version","status":"public","id":"12709"}]},"volume":189,"abstract":[{"lang":"eng","text":"Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness. "}],"oa_version":"Published Version","scopus_import":"1","alternative_title":["LIPIcs"],"month":"06","intvolume":" 189","date_updated":"2023-10-04T12:03:39Z","ddc":["516"],"file_date_updated":"2021-06-28T12:40:47Z","department":[{"_id":"HeEd"}],"_id":"9605","type":"conference","conference":{"start_date":"2021-06-07","end_date":"2021-06-11","location":"Online","name":"SoCG: International Symposium on Computational Geometry"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","has_accepted_license":"1","year":"2021","day":"02","publication":"Leibniz International Proceedings in Informatics","date_published":"2021-06-02T00:00:00Z","doi":"10.4230/LIPIcs.SoCG.2021.27","date_created":"2021-06-27T22:01:49Z","acknowledgement":"The authors want to thank the reviewers for many helpful comments and suggestions.","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"citation":{"ista":"Corbet R, Kerber M, Lesnick M, Osang GF. 2021. Computing the multicover bifiltration. Leibniz International Proceedings in Informatics. SoCG: International Symposium on Computational Geometry, LIPIcs, vol. 189, 27.","chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” In Leibniz International Proceedings in Informatics, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.SoCG.2021.27.","short":"R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ieee":"R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover bifiltration,” in Leibniz International Proceedings in Informatics, Online, 2021, vol. 189.","ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. In: Leibniz International Proceedings in Informatics. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.SoCG.2021.27","apa":"Corbet, R., Kerber, M., Lesnick, M., & Osang, G. F. (2021). Computing the multicover bifiltration. In Leibniz International Proceedings in Informatics (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2021.27","mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” Leibniz International Proceedings in Informatics, vol. 189, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.SoCG.2021.27."},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","author":[{"last_name":"Corbet","full_name":"Corbet, René","first_name":"René"},{"first_name":"Michael","last_name":"Kerber","full_name":"Kerber, Michael"},{"full_name":"Lesnick, Michael","last_name":"Lesnick","first_name":"Michael"},{"orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F","last_name":"Osang","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","first_name":"Georg F"}],"article_processing_charge":"No","external_id":{"arxiv":["2103.07823"]},"title":"Computing the multicover bifiltration","article_number":"27"},{"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","_id":"9441","type":"conference","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2021-06-07","end_date":"2021-06-11","location":"Virtual"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","date_updated":"2023-10-10T07:34:34Z","ddc":["005","516","514"],"file_date_updated":"2021-06-02T10:22:33Z","department":[{"_id":"HeEd"}],"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"}],"oa_version":"Published Version","alternative_title":["LIPIcs"],"place":"Dagstuhl, Germany","month":"06","intvolume":" 189","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-184-9"]},"publication_status":"published","file":[{"creator":"mwintrae","date_updated":"2021-06-02T10:22:33Z","file_size":1972902,"date_created":"2021-06-02T10:22:33Z","file_name":"LIPIcs-SoCG-2021-17.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"c322aa48d5d35a35877896cc565705b6","file_id":"9442","success":1}],"language":[{"iso":"eng"}],"volume":189,"related_material":{"record":[{"relation":"later_version","status":"public","id":"12960"}]},"ec_funded":1,"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"citation":{"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.","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.","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.","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","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","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.","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."},"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"full_name":"Kachanovich, Siargey","last_name":"Kachanovich","first_name":"Siargey"},{"first_name":"Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","last_name":"Wintraecken"}],"article_processing_charge":"No","title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter-Freudenthal-Kuhn triangulations","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.","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"has_accepted_license":"1","year":"2021","day":"02","publication":"37th International Symposium on Computational Geometry (SoCG 2021)","page":"17:1-17:16","doi":"10.4230/LIPIcs.SoCG.2021.17","date_published":"2021-06-02T00:00:00Z","date_created":"2021-06-02T10:10:55Z"},{"day":"01","publication":"Discrete and Computational Geometry","isi":1,"year":"2021","doi":"10.1007/s00454-020-00240-w","date_published":"2021-10-01T00:00:00Z","date_created":"2020-09-06T22:01:13Z","page":"938-976","acknowledgement":"This research was supported by the DFG Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”. W.K.S. was also supported by the Australian Research Council (DP1401000851). A.V.A. was also supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 78818 Alpha).","publisher":"Springer Nature","quality_controlled":"1","oa":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Akopyan, Arseniy, et al. “On Mutually Diagonal Nets on (Confocal) Quadrics and 3-Dimensional Webs.” Discrete and Computational Geometry, vol. 66, Springer Nature, 2021, pp. 938–76, doi:10.1007/s00454-020-00240-w.","short":"A. Akopyan, A.I. Bobenko, W.K. Schief, J. Techter, Discrete and Computational Geometry 66 (2021) 938–976.","ieee":"A. Akopyan, A. I. Bobenko, W. K. Schief, and J. Techter, “On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs,” Discrete and Computational Geometry, vol. 66. Springer Nature, pp. 938–976, 2021.","ama":"Akopyan A, Bobenko AI, Schief WK, Techter J. On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs. Discrete and Computational Geometry. 2021;66:938-976. doi:10.1007/s00454-020-00240-w","apa":"Akopyan, A., Bobenko, A. I., Schief, W. K., & Techter, J. (2021). On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00240-w","chicago":"Akopyan, Arseniy, Alexander I. Bobenko, Wolfgang K. Schief, and Jan Techter. “On Mutually Diagonal Nets on (Confocal) Quadrics and 3-Dimensional Webs.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00240-w.","ista":"Akopyan A, Bobenko AI, Schief WK, Techter J. 2021. On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs. Discrete and Computational Geometry. 66, 938–976."},"title":"On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs","author":[{"full_name":"Akopyan, Arseniy","orcid":"0000-0002-2548-617X","last_name":"Akopyan","first_name":"Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Bobenko, Alexander I.","last_name":"Bobenko","first_name":"Alexander I."},{"first_name":"Wolfgang K.","full_name":"Schief, Wolfgang K.","last_name":"Schief"},{"last_name":"Techter","full_name":"Techter, Jan","first_name":"Jan"}],"external_id":{"arxiv":["1908.00856"],"isi":["000564488500002"]},"article_processing_charge":"No","project":[{"name":"Alpha Shape Theory Extended","grant_number":"788183","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"published","volume":66,"ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Canonical parametrisations of classical confocal coordinate systems are introduced and exploited to construct non-planar analogues of incircular (IC) nets on individual quadrics and systems of confocal quadrics. Intimate connections with classical deformations of quadrics that are isometric along asymptotic lines and circular cross-sections of quadrics are revealed. The existence of octahedral webs of surfaces of Blaschke type generated by asymptotic and characteristic lines that are diagonally related to lines of curvature is proved theoretically and established constructively. Appropriate samplings (grids) of these webs lead to three-dimensional extensions of non-planar IC nets. Three-dimensional octahedral grids composed of planes and spatially extending (checkerboard) IC-nets are shown to arise in connection with systems of confocal quadrics in Minkowski space. In this context, the Laguerre geometric notion of conical octahedral grids of planes is introduced. The latter generalise the octahedral grids derived from systems of confocal quadrics in Minkowski space. An explicit construction of conical octahedral grids is presented. The results are accompanied by various illustrations which are based on the explicit formulae provided by the theory."}],"month":"10","intvolume":" 66","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1908.00856"}],"date_updated":"2024-03-07T14:51:11Z","department":[{"_id":"HeEd"}],"_id":"8338","status":"public","article_type":"original","type":"journal_article"},{"month":"09","intvolume":" 66","scopus_import":"1","main_file_link":[{"url":"https://doi.org/10.1007/s00454-020-00233-9","open_access":"1"}],"oa_version":"Published Version","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."}],"volume":66,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publication_status":"published","status":"public","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"8248","department":[{"_id":"HeEd"}],"ddc":["510"],"date_updated":"2024-03-07T14:54:59Z","publisher":"Springer Nature","quality_controlled":"1","oa":1,"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.","date_published":"2021-09-01T00:00:00Z","doi":"10.1007/s00454-020-00233-9","date_created":"2020-08-11T07:11:51Z","page":"666-686","day":"01","publication":"Discrete and Computational Geometry","has_accepted_license":"1","isi":1,"year":"2021","project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"title":"Local conditions for triangulating submanifolds of Euclidean space","author":[{"first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat"},{"first_name":"Ramsay","last_name":"Dyer","full_name":"Dyer, Ramsay"},{"first_name":"Arijit","last_name":"Ghosh","full_name":"Ghosh, Arijit"},{"first_name":"Andre","last_name":"Lieutier","full_name":"Lieutier, Andre"},{"orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs"}],"external_id":{"isi":["000558119300001"]},"article_processing_charge":"Yes (via OA deal)","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","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.","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.","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","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.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, M. Wintraecken, Discrete and Computational Geometry 66 (2021) 666–686.","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."}},{"day":"01","publication":"Discrete and Computational Geometry","isi":1,"has_accepted_license":"1","year":"2021","date_published":"2021-06-01T00:00:00Z","doi":"10.1007/s00454-020-00206-y","date_created":"2020-05-30T10:26:04Z","page":"1166-1198","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was partially supported by NSF IIS-1513616 and NSF ABI-1661375. The authors would like to thank the anonymous referees for their insightful comments.","quality_controlled":"1","publisher":"Springer Nature","oa":1,"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Brown, Adam, and Bei Wang. “Sheaf-Theoretic Stratification Learning from Geometric and Topological Perspectives.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00206-y.","ista":"Brown A, Wang B. 2021. Sheaf-theoretic stratification learning from geometric and topological perspectives. Discrete and Computational Geometry. 65, 1166–1198.","mla":"Brown, Adam, and Bei Wang. “Sheaf-Theoretic Stratification Learning from Geometric and Topological Perspectives.” Discrete and Computational Geometry, vol. 65, Springer Nature, 2021, pp. 1166–98, doi:10.1007/s00454-020-00206-y.","short":"A. Brown, B. Wang, Discrete and Computational Geometry 65 (2021) 1166–1198.","ieee":"A. Brown and B. Wang, “Sheaf-theoretic stratification learning from geometric and topological perspectives,” Discrete and Computational Geometry, vol. 65. Springer Nature, pp. 1166–1198, 2021.","apa":"Brown, A., & Wang, B. (2021). Sheaf-theoretic stratification learning from geometric and topological perspectives. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00206-y","ama":"Brown A, Wang B. Sheaf-theoretic stratification learning from geometric and topological perspectives. Discrete and Computational Geometry. 2021;65:1166-1198. doi:10.1007/s00454-020-00206-y"},"title":"Sheaf-theoretic stratification learning from geometric and topological perspectives","author":[{"last_name":"Brown","full_name":"Brown, Adam","first_name":"Adam","id":"70B7FDF6-608D-11E9-9333-8535E6697425"},{"first_name":"Bei","last_name":"Wang","full_name":"Wang, Bei"}],"external_id":{"isi":["000536324700001"],"arxiv":["1712.07734"]},"article_processing_charge":"Yes (via OA deal)","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"file":[{"file_id":"8803","checksum":"487a84ea5841b75f04f66d7ebd71b67e","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2020-11-25T09:06:41Z","file_name":"2020_DiscreteCompGeometry_Brown.pdf","creator":"dernst","date_updated":"2020-11-25T09:06:41Z","file_size":1013730}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publication_status":"published","volume":65,"oa_version":"Published Version","abstract":[{"text":"We investigate a sheaf-theoretic interpretation of stratification learning from geometric and topological perspectives. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1355–1370, ACM, New York, 2012), and the cohomology stratification algorithm given in Nanda (Found. Comput. Math. 20(2), 195–222, 2020). Additionally, we give examples of stratifications based on the geometric techniques of Breiding et al. (Rev. Mat. Complut. 31(3), 545–593, 2018), illustrating how the sheaf-theoretic approach can be used to study stratifications from both topological and geometric perspectives. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms.","lang":"eng"}],"month":"06","intvolume":" 65","scopus_import":"1","ddc":["510"],"date_updated":"2024-03-07T15:01:58Z","file_date_updated":"2020-11-25T09:06:41Z","department":[{"_id":"HeEd"}],"_id":"7905","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}},{"day":"01","publication":"Mathematics in Computer Science","has_accepted_license":"1","year":"2020","date_published":"2020-03-01T00:00:00Z","doi":"10.1007/s11786-020-00461-5","date_created":"2020-03-05T13:30:18Z","page":"141-176","quality_controlled":"1","publisher":"Springer Nature","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.” Mathematics in Computer Science. Springer Nature, 2020. https://doi.org/10.1007/s11786-020-00461-5.","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.","short":"A. Choudhary, S. Kachanovich, M. Wintraecken, Mathematics in Computer Science 14 (2020) 141–176.","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","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."},"title":"Coxeter triangulations have good quality","author":[{"last_name":"Choudhary","full_name":"Choudhary, Aruni","first_name":"Aruni"},{"last_name":"Kachanovich","full_name":"Kachanovich, Siargey","first_name":"Siargey"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken"}],"article_processing_charge":"Yes (via OA deal)","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"},{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"file":[{"creator":"dernst","date_updated":"2020-11-20T10:18:02Z","file_size":872275,"date_created":"2020-11-20T10:18:02Z","file_name":"2020_MathCompScie_Choudhary.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"8783","checksum":"1d145f3ab50ccee735983cb89236e609","success":1}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1661-8289"],"issn":["1661-8270"]},"publication_status":"published","volume":14,"ec_funded":1,"oa_version":"Published Version","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."}],"month":"03","intvolume":" 14","scopus_import":"1","ddc":["510"],"date_updated":"2021-01-12T08:14:13Z","file_date_updated":"2020-11-20T10:18:02Z","department":[{"_id":"HeEd"}],"_id":"7567","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}}]