[{"keyword":["Theoretical Computer Science","Computational Theory and Mathematics","Geometry and Topology","Discrete Mathematics and Combinatorics"],"quality_controlled":"1","_id":"8940","isi":1,"file":[{"relation":"main_file","date_updated":"2021-08-06T09:52:29Z","creator":"kschuh","file_id":"9795","date_created":"2021-08-06T09:52:29Z","checksum":"c848986091e56699dc12de85adb1e39c","file_size":983307,"success":1,"access_level":"open_access","content_type":"application/pdf","file_name":"2021_DescreteCompGeopmetry_Boissonnat.pdf"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Triangulating submanifolds: An elementary and quantified version of Whitney’s method","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"ec_funded":1,"ddc":["516"],"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."}],"oa":1,"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"issue":"1","date_created":"2020-12-12T11:07:02Z","publisher":"Springer Nature","date_updated":"2023-09-05T15:02:40Z","external_id":{"isi":["000597770300001"]},"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).","has_accepted_license":"1","article_type":"original","status":"public","day":"01","language":[{"iso":"eng"}],"year":"2021","department":[{"_id":"HeEd"}],"volume":66,"author":[{"last_name":"Boissonnat","first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel"},{"last_name":"Kachanovich","full_name":"Kachanovich, Siargey","first_name":"Siargey"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220"}],"license":"https://creativecommons.org/licenses/by/4.0/","article_processing_charge":"Yes (via OA deal)","doi":"10.1007/s00454-020-00250-8","type":"journal_article","publication_status":"published","page":"386-434","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","intvolume":" 66","file_date_updated":"2021-08-06T09:52:29Z","month":"07","citation":{"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","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","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete & Computational Geometry 66 (2021) 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.","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.","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.","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."},"publication":"Discrete & Computational Geometry","date_published":"2021-07-01T00:00:00Z"},{"oa_version":"Published Version","scopus_import":"1","file_date_updated":"2021-02-11T14:43:59Z","month":"03","intvolume":" 5","citation":{"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.","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.","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","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","short":"A. Brown, O. Bobrowski, E. Munch, B. Wang, Journal of Applied and Computational Topology 5 (2021) 99–140.","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."},"publication":"Journal of Applied and Computational Topology","date_published":"2021-03-01T00:00:00Z","article_processing_charge":"Yes (via OA deal)","doi":"10.1007/s41468-020-00063-x","type":"journal_article","publication_status":"published","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"page":"99-140","department":[{"_id":"HeEd"}],"volume":5,"author":[{"first_name":"Adam","full_name":"Brown, Adam","id":"70B7FDF6-608D-11E9-9333-8535E6697425","last_name":"Brown"},{"full_name":"Bobrowski, Omer","first_name":"Omer","last_name":"Bobrowski"},{"last_name":"Munch","first_name":"Elizabeth","full_name":"Munch, Elizabeth"},{"full_name":"Wang, Bei","first_name":"Bei","last_name":"Wang"}],"has_accepted_license":"1","article_type":"original","status":"public","year":"2021","language":[{"iso":"eng"}],"day":"01","date_created":"2021-02-11T14:41:02Z","publisher":"Springer Nature","date_updated":"2023-09-05T15:37:56Z","external_id":{"arxiv":["1909.03488"]},"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).","publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"ec_funded":1,"ddc":["510"],"abstract":[{"lang":"eng","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."}],"oa":1,"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"issue":"1","file":[{"date_updated":"2021-02-11T14:43:59Z","relation":"main_file","file_id":"9112","creator":"dernst","file_size":2090265,"checksum":"3f02e9d47c428484733da0f588a3c069","date_created":"2021-02-11T14:43:59Z","access_level":"open_access","success":1,"content_type":"application/pdf","file_name":"2020_JourApplCompTopology_Brown.pdf"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Probabilistic convergence and stability of random mapper graphs","quality_controlled":"1","_id":"9111"},{"has_accepted_license":"1","day":"01","language":[{"iso":"eng"}],"year":"2021","status":"public","department":[{"_id":"HeEd"},{"_id":"GradSch"}],"supervisor":[{"orcid":"0000-0002-9823-6833","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner"}],"author":[{"first_name":"Georg F","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","last_name":"Osang"}],"article_processing_charge":"No","doi":"10.15479/AT:ISTA:9056","type":"dissertation","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"page":"134","publication_status":"published","month":"02","file_date_updated":"2021-02-03T10:37:28Z","oa_version":"Published Version","date_published":"2021-02-01T00:00:00Z","citation":{"mla":"Osang, Georg F. Multi-Cover Persistence and Delaunay Mosaics. Institute of Science and Technology Austria, 2021, doi:10.15479/AT:ISTA:9056.","ieee":"G. F. Osang, “Multi-cover persistence and Delaunay mosaics,” Institute of Science and Technology Austria, Klosterneuburg, 2021.","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.","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","ama":"Osang GF. Multi-cover persistence and Delaunay mosaics. 2021. doi:10.15479/AT:ISTA:9056","short":"G.F. Osang, Multi-Cover Persistence and Delaunay Mosaics, Institute of Science and Technology Austria, 2021."},"alternative_title":["ISTA Thesis"],"_id":"9056","degree_awarded":"PhD","file":[{"date_created":"2021-02-02T14:09:25Z","checksum":"bcf27986147cab0533b6abadd74e7629","file_size":13446994,"date_updated":"2021-02-03T10:37:28Z","relation":"source_file","creator":"patrickd","file_id":"9063","file_name":"thesis_source.zip","access_level":"closed","content_type":"application/zip"},{"file_id":"9064","creator":"patrickd","date_updated":"2021-02-02T14:09:18Z","relation":"main_file","file_size":5210329,"checksum":"9cc8af266579a464385bbe2aff6af606","date_created":"2021-02-02T14:09:18Z","content_type":"application/pdf","success":1,"access_level":"open_access","file_name":"thesis_pdfA2b.pdf"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Multi-cover persistence and Delaunay mosaics","publication_identifier":{"issn":["2663-337X"]},"ddc":["006","514","516"],"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"}],"oa":1,"related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"187"},{"relation":"part_of_dissertation","status":"public","id":"8703"}]},"publisher":"Institute of Science and Technology Austria","date_created":"2021-02-02T14:11:06Z","place":"Klosterneuburg","date_updated":"2023-09-07T13:29:01Z"},{"quality_controlled":"1","_id":"10204","file":[{"access_level":"open_access","success":1,"content_type":"application/pdf","file_name":"2021_SoftMatter_acceptedversion_Osang.pdf","relation":"main_file","date_updated":"2023-10-03T09:21:42Z","creator":"dernst","file_id":"14385","date_created":"2023-10-03T09:21:42Z","checksum":"b4da0c420530295e61b153960f6cb350","file_size":4678788}],"isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Topological signatures and stability of hexagonal close packing and Barlow stackings","publication_identifier":{"eissn":["1744-6848"],"issn":["1744-683X"]},"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."}],"ddc":["540"],"ec_funded":1,"project":[{"call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","name":"Alpha Shape Theory Extended"},{"name":"The Wittgenstein Prize","grant_number":"Z00342","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"oa":1,"issue":"40","publisher":"Royal Society of Chemistry ","date_created":"2021-10-31T23:01:30Z","external_id":{"isi":["000700090000001"],"pmid":["34569592"]},"date_updated":"2023-10-03T09:24:27Z","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.","has_accepted_license":"1","article_type":"original","year":"2021","language":[{"iso":"eng"}],"day":"20","status":"public","department":[{"_id":"HeEd"}],"pmid":1,"volume":17,"author":[{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","last_name":"Osang","orcid":"0000-0002-8882-5116","first_name":"Georg F","full_name":"Osang, Georg F"},{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Saadatfar","full_name":"Saadatfar, Mohammad","first_name":"Mohammad"}],"article_processing_charge":"No","doi":"10.1039/d1sm00774b","type":"journal_article","page":"9107-9115","publication_status":"published","intvolume":" 17","file_date_updated":"2023-10-03T09:21:42Z","month":"10","oa_version":"Submitted Version","scopus_import":"1","date_published":"2021-10-20T00:00:00Z","publication":"Soft Matter","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.","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.","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.","short":"G.F. Osang, H. Edelsbrunner, M. Saadatfar, Soft Matter 17 (2021) 9107–9115.","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","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."}},{"language":[{"iso":"eng"}],"year":"2021","day":"02","status":"public","has_accepted_license":"1","author":[{"last_name":"Corbet","first_name":"René","full_name":"Corbet, René"},{"last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael"},{"last_name":"Lesnick","full_name":"Lesnick, Michael","first_name":"Michael"},{"last_name":"Osang","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","full_name":"Osang, Georg F","first_name":"Georg F","orcid":"0000-0002-8882-5116"}],"article_number":"27","department":[{"_id":"HeEd"}],"volume":189,"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publication_status":"published","article_processing_charge":"No","type":"conference","doi":"10.4230/LIPIcs.SoCG.2021.27","file_date_updated":"2021-06-28T12:40:47Z","month":"06","intvolume":" 189","oa_version":"Published Version","scopus_import":"1","date_published":"2021-06-02T00:00:00Z","publication":"Leibniz International Proceedings in Informatics","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.","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.","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.","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.","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","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"},"_id":"9605","alternative_title":["LIPIcs"],"quality_controlled":"1","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","title":"Computing the multicover bifiltration","file":[{"file_name":"2021_LIPIcs_Corbet.pdf","content_type":"application/pdf","success":1,"access_level":"open_access","date_created":"2021-06-28T12:40:47Z","checksum":"0de217501e7ba8b267d58deed0d51761","file_size":"1367983","creator":"cziletti","file_id":"9610","date_updated":"2021-06-28T12:40:47Z","relation":"main_file"}],"oa":1,"related_material":{"record":[{"relation":"later_version","status":"public","id":"12709"}],"link":[{"relation":"extended_version","url":"https://arxiv.org/abs/2103.07823"}]},"publication_identifier":{"issn":["18688969"],"isbn":["9783959771849"]},"ddc":["516"],"abstract":[{"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. ","lang":"eng"}],"external_id":{"arxiv":["2103.07823"]},"date_updated":"2023-10-04T12:03:39Z","acknowledgement":"The authors want to thank the reviewers for many helpful comments and suggestions.","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2021-06-27T22:01:49Z","conference":{"start_date":"2021-06-07","location":"Online","name":"SoCG: International Symposium on Computational Geometry","end_date":"2021-06-11"}}]