[{"license":"https://creativecommons.org/licenses/by/4.0/","type":"conference","scopus_import":"1","language":[{"iso":"eng"}],"date_published":"2021-06-02T00:00:00Z","publication":"Leibniz International Proceedings in Informatics","doi":"10.4230/LIPIcs.SoCG.2021.16","publication_identifier":{"isbn":["9783959771849"],"issn":["1868-8969"]},"article_number":"16","title":"Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory","year":"2021","intvolume":"       189","department":[{"_id":"HeEd"}],"article_processing_charge":"No","volume":189,"abstract":[{"lang":"eng","text":"Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation."}],"month":"06","status":"public","alternative_title":["LIPIcs"],"citation":{"ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory,” in <i>Leibniz International Proceedings in Informatics</i>, Online, 2021, vol. 189.","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2021. Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. Leibniz International Proceedings in Informatics. SoCG: International Symposium on Computational Geometry, LIPIcs, vol. 189, 16.","apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., &#38; Saghafian, M. (2021). Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. In <i>Leibniz International Proceedings in Informatics</i> (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">https://doi.org/10.4230/LIPIcs.SoCG.2021.16</a>","mla":"Biswas, Ranita, et al. “Counting Cells of Order-k Voronoi Tessellations in ℝ<sup>3</sup> with Morse Theory.” <i>Leibniz International Proceedings in Informatics</i>, vol. 189, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">10.4230/LIPIcs.SoCG.2021.16</a>.","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Counting Cells of Order-k Voronoi Tessellations in ℝ<sup>3</sup> with Morse Theory.” In <i>Leibniz International Proceedings in Informatics</i>, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">https://doi.org/10.4230/LIPIcs.SoCG.2021.16</a>.","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Counting cells of order-k voronoi tessellations in ℝ<sup>3</sup> with morse theory. In: <i>Leibniz International Proceedings in Informatics</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.16\">10.4230/LIPIcs.SoCG.2021.16</a>","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021."},"oa_version":"Published Version","file":[{"file_id":"9611","date_created":"2021-06-28T13:11:39Z","creator":"asandaue","relation":"main_file","access_level":"open_access","content_type":"application/pdf","date_updated":"2021-06-28T13:11:39Z","file_size":727817,"file_name":"2021_LIPIcs_Biswas.pdf","checksum":"22b11a719018b22ecba2471b51f2eb40","success":1}],"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)"},"ec_funded":1,"date_created":"2021-06-27T22:01:48Z","date_updated":"2025-07-10T12:01:56Z","project":[{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"call_identifier":"FWF","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science"},{"name":"Persistent Homology, Algorithms and Stochastic Geometry","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","grant_number":"I4887"}],"day":"02","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"orcid":"0000-0002-5372-7890","last_name":"Biswas","full_name":"Biswas, Ranita","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","first_name":"Ranita"},{"full_name":"Cultrera di Montesano, Sebastiano","last_name":"Cultrera di Montesano","orcid":"0000-0001-6249-0832","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","first_name":"Sebastiano"},{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Morteza","full_name":"Saghafian, Morteza","last_name":"Saghafian"}],"_id":"9604","has_accepted_license":"1","ddc":["516"],"oa":1,"file_date_updated":"2021-06-28T13:11:39Z","conference":{"start_date":"2021-06-07","name":"SoCG: International Symposium on Computational Geometry","location":"Online","end_date":"2021-06-11"}},{"department":[{"_id":"HeEd"}],"volume":189,"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"}],"month":"06","article_processing_charge":"No","status":"public","related_material":{"link":[{"url":"https://arxiv.org/abs/2103.07823","relation":"extended_version"}],"record":[{"id":"12709","status":"public","relation":"later_version"}]},"citation":{"chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” In <i>Leibniz International Proceedings in Informatics</i>, Vol. 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">https://doi.org/10.4230/LIPIcs.SoCG.2021.27</a>.","mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” <i>Leibniz International Proceedings in Informatics</i>, vol. 189, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">10.4230/LIPIcs.SoCG.2021.27</a>.","apa":"Corbet, R., Kerber, M., Lesnick, M., &#38; Osang, G. F. (2021). Computing the multicover bifiltration. In <i>Leibniz International Proceedings in Informatics</i> (Vol. 189). Online: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">https://doi.org/10.4230/LIPIcs.SoCG.2021.27</a>","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 <i>Leibniz International Proceedings in Informatics</i>, Online, 2021, vol. 189.","short":"R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. In: <i>Leibniz International Proceedings in Informatics</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.27\">10.4230/LIPIcs.SoCG.2021.27</a>"},"alternative_title":["LIPIcs"],"file":[{"content_type":"application/pdf","file_name":"2021_LIPIcs_Corbet.pdf","file_size":"1367983","date_updated":"2021-06-28T12:40:47Z","checksum":"0de217501e7ba8b267d58deed0d51761","success":1,"file_id":"9610","date_created":"2021-06-28T12:40:47Z","creator":"cziletti","relation":"main_file","access_level":"open_access"}],"oa_version":"Published Version","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)"},"date_created":"2021-06-27T22:01:49Z","type":"conference","date_published":"2021-06-02T00:00:00Z","language":[{"iso":"eng"}],"publication":"Leibniz International Proceedings in Informatics","scopus_import":"1","doi":"10.4230/LIPIcs.SoCG.2021.27","article_number":"27","arxiv":1,"publication_identifier":{"isbn":["9783959771849"],"issn":["1868-8969"]},"title":"Computing the multicover bifiltration","intvolume":"       189","year":"2021","acknowledgement":"The authors want to thank the reviewers for many helpful comments and suggestions.","quality_controlled":"1","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","has_accepted_license":"1","ddc":["516"],"author":[{"last_name":"Corbet","full_name":"Corbet, René","first_name":"René"},{"full_name":"Kerber, Michael","last_name":"Kerber","first_name":"Michael"},{"first_name":"Michael","full_name":"Lesnick, Michael","last_name":"Lesnick"},{"full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","last_name":"Osang","first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}],"_id":"9605","conference":{"end_date":"2021-06-11","location":"Online","start_date":"2021-06-07","name":"SoCG: International Symposium on Computational Geometry"},"file_date_updated":"2021-06-28T12:40:47Z","oa":1,"date_updated":"2025-07-10T12:01:57Z","external_id":{"arxiv":["2103.07823"]},"day":"02","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"publication_status":"published","quality_controlled":"1","oa":1,"conference":{"end_date":"2020-09-09","location":"Pisa, Italy","name":"ESA: Annual European Symposium on Algorithms","start_date":"2020-09-07"},"author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"first_name":"Khan","full_name":"Shahbaz, Khan","last_name":"Shahbaz"},{"first_name":"Richard","last_name":"Paul","full_name":"Paul, Richard"},{"full_name":"Schulz, Christian","last_name":"Schulz","first_name":"Christian"}],"_id":"11816","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_updated":"2024-11-06T08:23:03Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2020.58"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"26","external_id":{"arxiv":["2004.09099"]},"status":"public","article_processing_charge":"No","abstract":[{"lang":"eng","text":"In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances."}],"month":"08","volume":173,"date_created":"2022-08-12T07:13:25Z","oa_version":"Published Version","extern":"1","alternative_title":["LIPIcs"],"citation":{"apa":"Henzinger, M., Shahbaz, K., Paul, R., &#38; Schulz, C. (2020). Dynamic matching algorithms in practice. In <i>8th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>","mla":"Henzinger, Monika, et al. “Dynamic Matching Algorithms in Practice.” <i>8th Annual European Symposium on Algorithms</i>, vol. 173, 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>.","chicago":"Henzinger, Monika, Khan Shahbaz, Richard Paul, and Christian Schulz. “Dynamic Matching Algorithms in Practice.” In <i>8th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>.","ieee":"M. Henzinger, K. Shahbaz, R. Paul, and C. Schulz, “Dynamic matching algorithms in practice,” in <i>8th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","ista":"Henzinger M, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.","ama":"Henzinger M, Shahbaz K, Paul R, Schulz C. Dynamic matching algorithms in practice. In: <i>8th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>","short":"M. Henzinger, K. Shahbaz, R. Paul, C. Schulz, in:, 8th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"doi":"10.4230/LIPIcs.ESA.2020.58","scopus_import":"1","publication":"8th Annual European Symposium on Algorithms","date_published":"2020-08-26T00:00:00Z","language":[{"iso":"eng"}],"type":"conference","year":"2020","intvolume":"       173","title":"Dynamic matching algorithms in practice","article_number":"58","publication_identifier":{"isbn":["9783959771627"],"issn":["1868-8969"]},"arxiv":1},{"external_id":{"arxiv":["2004.14891"]},"day":"26","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-11-06T08:22:13Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2020.57"}],"oa":1,"conference":{"end_date":"2020-09-09","location":"Pisa, Italy","start_date":"2020-09-07","name":"ESA: Annual European Symposium on Algorithms"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"11818","author":[{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"first_name":"Sagar","full_name":"Kale, Sagar","last_name":"Kale"}],"publication_status":"published","quality_controlled":"1","year":"2020","intvolume":"       173","arxiv":1,"article_number":"57","publication_identifier":{"isbn":["9783959771627"],"issn":["1868-8969"]},"title":"Fully-dynamic coresets","doi":"10.4230/LIPIcs.ESA.2020.57","type":"conference","scopus_import":"1","language":[{"iso":"eng"}],"publication":"28th Annual European Symposium on Algorithms","date_published":"2020-08-26T00:00:00Z","date_created":"2022-08-12T07:22:55Z","alternative_title":["LIPIcs"],"extern":"1","citation":{"apa":"Henzinger, M., &#38; Kale, S. (2020). Fully-dynamic coresets. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>","mla":"Henzinger, Monika, and Sagar Kale. “Fully-Dynamic Coresets.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>.","chicago":"Henzinger, Monika, and Sagar Kale. “Fully-Dynamic Coresets.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>.","ista":"Henzinger M, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.","ieee":"M. Henzinger and S. Kale, “Fully-dynamic coresets,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","ama":"Henzinger M, Kale S. Fully-dynamic coresets. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>","short":"M. Henzinger, S. Kale, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"oa_version":"Published Version","status":"public","article_processing_charge":"No","abstract":[{"lang":"eng","text":"With input sizes becoming massive, coresets - small yet representative summary of the input - are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1±ε] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static (i.e., not dynamic) ε-coreset-construction algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1-λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) ⋅ t(s(n, ε/log n, λ/n), ε/log n, λ/n)) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique, which is due to Har-Peled and Mazumdar [Har-Peled and Mazumdar, 2004] and is based on a technique of Bentley and Saxe [Jon Louis Bentley and James B. Saxe, 1980], that applies to the insertion-only setting where points can only be added. Although, our space usage is O(n), our technique works in the presence of an adaptive adversary, and we show that Ω(n) space is required when adversary is adaptive.\r\nAs a concrete implication of our technique, using the result of Braverman et al. [{Braverman} et al., 2016], we get fully-dynamic ε-coreset-construction algorithms for k-median and k-means with worst-case update time O(ε^{-2} k² log⁵ n log³ k) and coreset size O(ε^{-2} k log n log² k) ignoring log log n and log(1/ε) factors and assuming that ε = Ω(1/poly(n)) and λ = Ω(1/poly(n)) (which are very weak assumptions made only to make these bounds easy to parse). This results in the first fully-dynamic constant-approximation algorithms for k-median and k-means with update times O(poly(k, log n, ε^{-1})). Specifically, the dependence on k is only quadratic, and the bounds are worst-case. The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. [Cohen-Addad et al., 2019] via randomized O(1)-coresets in O(n) space.\r\nWe also show that under the OMv conjecture [Monika Henzinger et al., 2015], a fully-dynamic (4 - δ)-approximation algorithm for k-means must either have an amortized update time of Ω(k^{1-γ}) or amortized query time of Ω(k^{2 - γ}), where γ > 0 is a constant."}],"month":"08","volume":173},{"oa":1,"conference":{"location":"Pisa, Italy","end_date":"2020-09-09","start_date":"2020-09-07","name":"ESA: Annual European Symposium on Algorithms"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"11819","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"last_name":"Noe","full_name":"Noe, Alexander","first_name":"Alexander"},{"first_name":"Christian","full_name":"Schulz, Christian","last_name":"Schulz"},{"last_name":"Strash","full_name":"Strash, Darren","first_name":"Darren"}],"publication_status":"published","quality_controlled":"1","external_id":{"arxiv":["2002.06948"]},"day":"26","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-11-06T08:23:16Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2020.59"}],"date_created":"2022-08-12T07:27:42Z","extern":"1","alternative_title":["LIPIcs"],"citation":{"ama":"Henzinger M, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>","short":"M. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Henzinger M, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.","ieee":"M. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","apa":"Henzinger, M., Noe, A., Schulz, C., &#38; Strash, D. (2020). Finding all global minimum cuts in practice. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>","mla":"Henzinger, Monika, et al. “Finding All Global Minimum Cuts in Practice.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>.","chicago":"Henzinger, Monika, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>."},"oa_version":"Published Version","status":"public","article_processing_charge":"No","month":"08","abstract":[{"text":"We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.","lang":"eng"}],"volume":173,"year":"2020","intvolume":"       173","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"article_number":"59","arxiv":1,"title":"Finding all global minimum cuts in practice","doi":"10.4230/LIPIcs.ESA.2020.59","type":"conference","scopus_import":"1","language":[{"iso":"eng"}],"publication":"28th Annual European Symposium on Algorithms","date_published":"2020-08-26T00:00:00Z"},{"quality_controlled":"1","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"11822","author":[{"full_name":"Hanauer, Kathrin","last_name":"Hanauer","first_name":"Kathrin"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"}],"oa":1,"conference":{"name":"SEA: Symposium on Experimental Algorithms","start_date":"2020-09-07","end_date":"2020-09-09","location":"Pisa, Italy"},"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.SEA.2020.14","open_access":"1"}],"date_updated":"2024-11-06T11:57:02Z","day":"12","external_id":{"arxiv":["2002.00813"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","month":"06","volume":160,"abstract":[{"text":"The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered.\r\nIn this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.","lang":"eng"}],"status":"public","extern":"1","alternative_title":["LIPIcs"],"citation":{"ama":"Hanauer K, Henzinger M, Schulz C. Faster fully dynamic transitive closure in practice. In: <i>18th International Symposium on Experimental Algorithms</i>. Vol 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">10.4230/LIPIcs.SEA.2020.14</a>","short":"K. Hanauer, M. Henzinger, C. Schulz, in:, 18th International Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"K. Hanauer, M. Henzinger, and C. Schulz, “Faster fully dynamic transitive closure in practice,” in <i>18th International Symposium on Experimental Algorithms</i>, Pisa, Italy, 2020, vol. 160.","ista":"Hanauer K, Henzinger M, Schulz C. 2020. Faster fully dynamic transitive closure in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 160, 14.","mla":"Hanauer, Kathrin, et al. “Faster Fully Dynamic Transitive Closure in Practice.” <i>18th International Symposium on Experimental Algorithms</i>, vol. 160, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">10.4230/LIPIcs.SEA.2020.14</a>.","apa":"Hanauer, K., Henzinger, M., &#38; Schulz, C. (2020). Faster fully dynamic transitive closure in practice. In <i>18th International Symposium on Experimental Algorithms</i> (Vol. 160). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>","chicago":"Hanauer, Kathrin, Monika Henzinger, and Christian Schulz. “Faster Fully Dynamic Transitive Closure in Practice.” In <i>18th International Symposium on Experimental Algorithms</i>, Vol. 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>."},"oa_version":"Published Version","date_created":"2022-08-12T07:32:53Z","type":"conference","scopus_import":"1","publication":"18th International Symposium on Experimental Algorithms","date_published":"2020-06-12T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SEA.2020.14","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771481"]},"arxiv":1,"article_number":"14","title":"Faster fully dynamic transitive closure in practice","year":"2020","intvolume":"       160"},{"status":"public","abstract":[{"text":"Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect.\r\nWe present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results:\r\n- For weighted intervals, we maintain a (1+ε)-approximate solution.\r\n- For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds.\r\n- For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N.","lang":"eng"}],"month":"06","volume":164,"article_processing_charge":"No","date_created":"2022-08-12T07:46:44Z","oa_version":"Published Version","citation":{"ista":"Henzinger M, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.","ieee":"M. Henzinger, S. Neumann, and A. Wiese, “Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles,” in <i>36th International Symposium on Computational Geometry</i>, Zurich, Switzerland, 2020, vol. 164.","chicago":"Henzinger, Monika, Stefan Neumann, and Andreas Wiese. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">https://doi.org/10.4230/LIPIcs.SoCG.2020.51</a>.","apa":"Henzinger, M., Neumann, S., &#38; Wiese, A. (2020). Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zurich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">https://doi.org/10.4230/LIPIcs.SoCG.2020.51</a>","mla":"Henzinger, Monika, et al. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">10.4230/LIPIcs.SoCG.2020.51</a>.","short":"M. Henzinger, S. Neumann, A. Wiese, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Henzinger M, Neumann S, Wiese A. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">10.4230/LIPIcs.SoCG.2020.51</a>"},"alternative_title":["LIPIcs"],"extern":"1","doi":"10.4230/LIPIcs.SoCG.2020.51","publication":"36th International Symposium on Computational Geometry","language":[{"iso":"eng"}],"date_published":"2020-06-08T00:00:00Z","scopus_import":"1","type":"conference","intvolume":"       164","year":"2020","title":"Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles","arxiv":1,"publication_identifier":{"isbn":["9783959771436"],"issn":["1868-8969"]},"article_number":"51","publication_status":"published","quality_controlled":"1","conference":{"location":"Zurich, Switzerland","end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry","start_date":"2020-06-23"},"oa":1,"author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"first_name":"Stefan","last_name":"Neumann","full_name":"Neumann, Stefan"},{"last_name":"Wiese","full_name":"Wiese, Andreas","first_name":"Andreas"}],"_id":"11824","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_updated":"2024-11-06T11:56:49Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.SoCG.2020.51"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2003.02605"]},"day":"08"},{"publication_status":"published","quality_controlled":"1","conference":{"start_date":"2020-03-10","name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2020-03-13","location":"Montpellier, France"},"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"first_name":"Pan","last_name":"Peng","full_name":"Peng, Pan"}],"_id":"11825","date_updated":"2024-11-06T11:57:29Z","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.STACS.2020.53","open_access":"1"}],"external_id":{"arxiv":["1907.04745"]},"day":"04","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","abstract":[{"lang":"eng","text":"We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω(log n) time per operation."}],"month":"03","volume":154,"article_processing_charge":"No","date_created":"2022-08-12T07:53:05Z","citation":{"ama":"Henzinger M, Peng P. Constant-time dynamic (Δ+1)-coloring. In: <i>37th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>","short":"M. Henzinger, P. Peng, in:, 37th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Henzinger M, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53.","ieee":"M. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Montpellier, France, 2020, vol. 154.","mla":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 154, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>.","apa":"Henzinger, M., &#38; Peng, P. (2020). Constant-time dynamic (Δ+1)-coloring. In <i>37th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 154). Montpellier, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>","chicago":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” In <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>."},"extern":"1","alternative_title":["LIPIcs"],"oa_version":"Published Version","doi":"10.4230/LIPIcs.STACS.2020.53","type":"conference","date_published":"2020-03-04T00:00:00Z","publication":"37th International Symposium on Theoretical Aspects of Computer Science","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":"       154","year":"2020","arxiv":1,"article_number":"53","publication_identifier":{"isbn":["9783959771405"],"issn":["1868-8969"]},"title":"Constant-time dynamic (Δ+1)-coloring"},{"_id":"7605","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Fedorov, Alexander","last_name":"Fedorov","first_name":"Alexander"},{"first_name":"Nikita","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","full_name":"Koval, Nikita","last_name":"Koval"}],"ddc":["000"],"has_accepted_license":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"file_date_updated":"2020-07-14T12:48:01Z","conference":{"location":"Neuchatal, Switzerland","end_date":"2019-12-19","name":"OPODIS: International Conference on Principles of Distributed Systems","start_date":"2019-12-17"},"corr_author":"1","quality_controlled":"1","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","external_id":{"arxiv":["1911.06347"]},"date_updated":"2025-07-10T11:54:46Z","page":"15:1-15:16","oa_version":"Published Version","file":[{"file_id":"7609","date_created":"2020-03-23T09:22:48Z","creator":"dernst","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":13074131,"date_updated":"2020-07-14T12:48:01Z","file_name":"2019_LIPIcs_Alistarh.pdf","checksum":"d66f07ecb609d9f02433e39f80a447e9"}],"alternative_title":["LIPIcs"],"citation":{"short":"D.-A. Alistarh, A. Fedorov, N. Koval, in:, 23rd International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16.","ama":"Alistarh D-A, Fedorov A, Koval N. In search of the fastest concurrent union-find algorithm. In: <i>23rd International Conference on Principles of Distributed Systems</i>. Vol 153. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:15:1-15:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">10.4230/LIPIcs.OPODIS.2019.15</a>","chicago":"Alistarh, Dan-Adrian, Alexander Fedorov, and Nikita Koval. “In Search of the Fastest Concurrent Union-Find Algorithm.” In <i>23rd International Conference on Principles of Distributed Systems</i>, 153:15:1-15:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2019.15</a>.","apa":"Alistarh, D.-A., Fedorov, A., &#38; Koval, N. (2020). In search of the fastest concurrent union-find algorithm. In <i>23rd International Conference on Principles of Distributed Systems</i> (Vol. 153, p. 15:1-15:16). Neuchatal, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2019.15</a>","mla":"Alistarh, Dan-Adrian, et al. “In Search of the Fastest Concurrent Union-Find Algorithm.” <i>23rd International Conference on Principles of Distributed Systems</i>, vol. 153, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 15:1-15:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2019.15\">10.4230/LIPIcs.OPODIS.2019.15</a>.","ista":"Alistarh D-A, Fedorov A, Koval N. 2020. In search of the fastest concurrent union-find algorithm. 23rd International Conference on Principles of Distributed Systems. OPODIS: International Conference on Principles of Distributed Systems, LIPIcs, vol. 153, 15:1-15:16.","ieee":"D.-A. Alistarh, A. Fedorov, and N. Koval, “In search of the fastest concurrent union-find algorithm,” in <i>23rd International Conference on Principles of Distributed Systems</i>, Neuchatal, Switzerland, 2020, vol. 153, p. 15:1-15:16."},"date_created":"2020-03-22T23:00:46Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"article_processing_charge":"No","abstract":[{"text":"Union-Find (or Disjoint-Set Union) is one of the fundamental problems in computer science; it has been well-studied from both theoretical and practical perspectives in the sequential case. Recently, there has been mounting interest in analyzing this problem in the concurrent scenario, and several asymptotically-efficient algorithms have been proposed. Yet, to date, there is very little known about the practical performance of concurrent Union-Find. This work addresses this gap. We evaluate and analyze the performance of several concurrent Union-Find algorithms and optimization strategies across a wide range of platforms (Intel, AMD, and ARM) and workloads (social, random, and road networks, as well as integrations into more complex algorithms). We first observe that, due to the limited computational cost, the number of induced cache misses is the critical determining factor for the performance of existing algorithms. We introduce new techniques to reduce this cost by storing node priorities implicitly and by using plain reads and writes in a way that does not affect the correctness of the algorithms. Finally, we show that Union-Find implementations are an interesting application for Transactional Memory (TM): one of the fastest algorithm variants we discovered is a sequential one that uses coarse-grained locking with the lock elision optimization to reduce synchronization cost and increase scalability. ","lang":"eng"}],"volume":153,"month":"02","department":[{"_id":"DaAl"}],"status":"public","title":"In search of the fastest concurrent union-find algorithm","arxiv":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771337"]},"year":"2020","intvolume":"       153","scopus_import":"1","publication":"23rd International Conference on Principles of Distributed Systems","date_published":"2020-02-01T00:00:00Z","language":[{"iso":"eng"}],"type":"conference","license":"https://creativecommons.org/licenses/by/3.0/","doi":"10.4230/LIPIcs.OPODIS.2019.15"},{"date_updated":"2025-04-22T13:45:17Z","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","corr_author":"1","quality_controlled":"1","publication_status":"published","author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"_id":"7952","has_accepted_license":"1","ddc":["510"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:48:06Z","oa":1,"conference":{"end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"scopus_import":"1","date_published":"2020-06-01T00:00:00Z","language":[{"iso":"eng"}],"publication":"36th International Symposium on Computational Geometry","type":"conference","doi":"10.4230/LIPIcs.SoCG.2020.20","title":"The topological correctness of PL-approximations of isomanifolds","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-143-6"]},"article_number":"20:1-20:18","year":"2020","intvolume":"       164","article_processing_charge":"No","month":"06","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. "}],"volume":164,"department":[{"_id":"HeEd"}],"related_material":{"record":[{"id":"9649","status":"public","relation":"later_version"}]},"status":"public","oa_version":"Published Version","file":[{"access_level":"open_access","date_created":"2020-06-17T10:13:34Z","creator":"dernst","relation":"main_file","file_id":"7969","checksum":"38cbfa4f5d484d267a35d44d210df044","content_type":"application/pdf","date_updated":"2020-07-14T12:48:06Z","file_size":1009739,"file_name":"2020_LIPIcsSoCG_Boissonnat.pdf"}],"alternative_title":["LIPIcs"],"citation":{"ieee":"J.-D. Boissonnat and M. Wintraecken, “The topological correctness of PL-approximations of isomanifolds,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","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.","apa":"Boissonnat, J.-D., &#38; Wintraecken, M. (2020). The topological correctness of PL-approximations of isomanifolds. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">https://doi.org/10.4230/LIPIcs.SoCG.2020.20</a>","mla":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">10.4230/LIPIcs.SoCG.2020.20</a>.","chicago":"Boissonnat, Jean-Daniel, and Mathijs Wintraecken. “The Topological Correctness of PL-Approximations of Isomanifolds.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">https://doi.org/10.4230/LIPIcs.SoCG.2020.20</a>.","ama":"Boissonnat J-D, Wintraecken M. The topological correctness of PL-approximations of isomanifolds. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.20\">10.4230/LIPIcs.SoCG.2020.20</a>","short":"J.-D. Boissonnat, M. Wintraecken, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"ec_funded":1,"date_created":"2020-06-09T07:24:11Z","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)"}},{"quality_controlled":"1","corr_author":"1","publication_status":"published","_id":"7989","author":[{"orcid":"0000-0002-3975-1683","last_name":"Patakova","full_name":"Patakova, Zuzana","first_name":"Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87"}],"has_accepted_license":"1","ddc":["510"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"file_date_updated":"2020-07-14T12:48:06Z","conference":{"location":"Zürich, Switzerland","end_date":"2020-06-26","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"date_updated":"2025-07-10T11:54:54Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","external_id":{"arxiv":["1908.01677"]},"article_processing_charge":"No","abstract":[{"lang":"eng","text":"We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface."}],"month":"06","volume":164,"department":[{"_id":"UlWa"}],"status":"public","oa_version":"Published Version","file":[{"checksum":"d0996ca5f6eb32ce955ce782b4f2afbe","content_type":"application/pdf","file_size":645421,"file_name":"2020_LIPIcsSoCG_Patakova_61.pdf","date_updated":"2020-07-14T12:48:06Z","access_level":"open_access","file_id":"8005","creator":"dernst","date_created":"2020-06-23T06:56:23Z","relation":"main_file"}],"alternative_title":["LIPIcs"],"citation":{"ama":"Patakova Z. Bounding radon number via Betti numbers. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.61\">10.4230/LIPIcs.SoCG.2020.61</a>","short":"Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","apa":"Patakova, Z. (2020). Bounding radon number via Betti numbers. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.61\">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>","mla":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.61\">10.4230/LIPIcs.SoCG.2020.61</a>.","chicago":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.61\">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>.","ieee":"Z. Patakova, “Bounding radon number via Betti numbers,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","ista":"Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 61:1-61:13."},"date_created":"2020-06-22T09:14:18Z","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)"},"scopus_import":"1","date_published":"2020-06-01T00:00:00Z","language":[{"iso":"eng"}],"publication":"36th International Symposium on Computational Geometry","type":"conference","doi":"10.4230/LIPIcs.SoCG.2020.61","title":"Bounding radon number via Betti numbers","article_number":"61:1-61:13","arxiv":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771436"]},"year":"2020","intvolume":"       164"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","external_id":{"arxiv":["2003.13557"]},"date_updated":"2025-07-10T11:54:56Z","author":[{"orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"},{"first_name":"Emo","full_name":"Welzl, Emo","last_name":"Welzl"}],"_id":"7990","ddc":["510"],"has_accepted_license":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2020-07-14T12:48:06Z","oa":1,"conference":{"end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"quality_controlled":"1","corr_author":"1","publication_status":"published","title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771436"]},"arxiv":1,"article_number":"67:1 - 67:16","year":"2020","intvolume":"       164","scopus_import":"1","date_published":"2020-06-01T00:00:00Z","publication":"36th International Symposium on Computational Geometry","language":[{"iso":"eng"}],"type":"conference","doi":"10.4230/LIPIcs.SoCG.2020.67","oa_version":"Published Version","file":[{"file_id":"8003","relation":"main_file","date_created":"2020-06-23T06:37:27Z","creator":"dernst","access_level":"open_access","file_size":793187,"file_name":"2020_LIPIcsSoCG_Wagner.pdf","date_updated":"2020-07-14T12:48:06Z","content_type":"application/pdf","checksum":"3f6925be5f3dcdb3b14cab92f410edf7"}],"alternative_title":["LIPIcs"],"citation":{"short":"U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">10.4230/LIPIcs.SoCG.2020.67</a>","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">10.4230/LIPIcs.SoCG.2020.67</a>.","apa":"Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>","ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 67:1-67:16.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164."},"date_created":"2020-06-22T09:14:19Z","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_processing_charge":"No","month":"06","volume":164,"abstract":[{"lang":"eng","text":"Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction)."}],"department":[{"_id":"UlWa"}],"related_material":{"record":[{"status":"public","id":"12129","relation":"later_version"}]},"status":"public"},{"oa":1,"file_date_updated":"2020-07-14T12:48:06Z","conference":{"end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"7991","author":[{"last_name":"Avvakumov","orcid":"0000-0002-7840-5062","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey"},{"full_name":"Nivasch, Gabriel","last_name":"Nivasch","first_name":"Gabriel"}],"has_accepted_license":"1","ddc":["510"],"publication_status":"published","quality_controlled":"1","day":"01","external_id":{"arxiv":["1909.00263"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","call_identifier":"FWF"}],"date_updated":"2025-07-10T11:54:56Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"date_created":"2020-06-22T09:14:19Z","alternative_title":["LIPIcs"],"citation":{"ista":"Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening flow. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 12:1-12:15.","ieee":"S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening flow,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","mla":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">10.4230/LIPIcs.SoCG.2020.12</a>.","apa":"Avvakumov, S., &#38; Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>","chicago":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>.","ama":"Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">10.4230/LIPIcs.SoCG.2020.12</a>","short":"S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"oa_version":"Published Version","file":[{"content_type":"application/pdf","file_name":"2020_LIPIcsSoCG_Avvakumov.pdf","file_size":575896,"date_updated":"2020-07-14T12:48:06Z","checksum":"6872df6549142f709fb6354a1b2f2c06","date_created":"2020-06-23T11:13:49Z","creator":"dernst","relation":"main_file","file_id":"8007","access_level":"open_access"}],"status":"public","department":[{"_id":"UlWa"}],"article_processing_charge":"No","month":"06","volume":164,"abstract":[{"lang":"eng","text":"We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between \"grid peeling\" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase."}],"year":"2020","intvolume":"       164","publication_identifier":{"isbn":["9783959771436"],"issn":["1868-8969"]},"arxiv":1,"article_number":"12:1 - 12:15","title":"Homotopic curve shortening and the affine curve-shortening flow","doi":"10.4230/LIPIcs.SoCG.2020.12","type":"conference","scopus_import":"1","publication":"36th International Symposium on Computational Geometry","date_published":"2020-06-01T00:00:00Z","language":[{"iso":"eng"}]},{"year":"2020","intvolume":"       164","publication_identifier":{"isbn":["9783959771436"],"issn":["1868-8969"]},"article_number":"62:1 - 62:16","arxiv":1,"title":"Barycentric cuts through a convex body","doi":"10.4230/LIPIcs.SoCG.2020.62","type":"conference","scopus_import":"1","date_published":"2020-06-01T00:00:00Z","publication":"36th International Symposium on Computational Geometry","language":[{"iso":"eng"}],"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)"},"date_created":"2020-06-22T09:14:20Z","alternative_title":["LIPIcs"],"citation":{"ista":"Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 62:1-62:16.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","apa":"Patakova, Z., Tancer, M., &#38; Wagner, U. (2020). Barycentric cuts through a convex body. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">10.4230/LIPIcs.SoCG.2020.62</a>.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">10.4230/LIPIcs.SoCG.2020.62</a>","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"oa_version":"Published Version","file":[{"access_level":"open_access","file_id":"8004","relation":"main_file","creator":"dernst","date_created":"2020-06-23T06:45:52Z","checksum":"ce1c9194139a664fb59d1efdfc88eaae","file_size":750318,"file_name":"2020_LIPIcsSoCG_Patakova.pdf","date_updated":"2020-07-14T12:48:06Z","content_type":"application/pdf"}],"status":"public","department":[{"_id":"UlWa"}],"article_processing_charge":"No","month":"06","volume":164,"abstract":[{"text":"Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.","lang":"eng"}],"external_id":{"arxiv":["2003.13536"]},"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-07-10T11:54:57Z","oa":1,"file_date_updated":"2020-07-14T12:48:06Z","conference":{"start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry","location":"Zürich, Switzerland","end_date":"2020-06-26"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"full_name":"Patakova, Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana"},{"full_name":"Tancer, Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"_id":"7992","has_accepted_license":"1","ddc":["510"],"publication_status":"published","quality_controlled":"1","corr_author":"1"},{"abstract":[{"text":"In the recent study of crossing numbers, drawings of graphs that can be extended to an arrangement of pseudolines (pseudolinear drawings) have played an important role as they are a natural combinatorial extension of rectilinear (or straight-line) drawings. A characterization of the pseudolinear drawings of K_n was found recently. We extend this characterization to all graphs, by describing the set of minimal forbidden subdrawings for pseudolinear drawings. Our characterization also leads to a polynomial-time algorithm to recognize pseudolinear drawings and construct the pseudolines when it is possible.","lang":"eng"}],"month":"06","volume":164,"article_processing_charge":"No","department":[{"_id":"UlWa"}],"status":"public","file":[{"date_created":"2020-06-23T11:06:23Z","creator":"dernst","relation":"main_file","file_id":"8006","access_level":"open_access","content_type":"application/pdf","file_size":592661,"file_name":"2020_LIPIcsSoCG_Arroyo.pdf","date_updated":"2020-07-14T12:48:06Z","checksum":"93571b76cf97d5b7c8aabaeaa694dd7e"}],"oa_version":"Published Version","citation":{"short":"A.M. Arroyo Guevara, J. Bensmail, R. Bruce Richter, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs to arrangements of pseudolines. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">10.4230/LIPIcs.SoCG.2020.9</a>","chicago":"Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending Drawings of Graphs to Arrangements of Pseudolines.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>.","apa":"Arroyo Guevara, A. M., Bensmail, J., &#38; Bruce Richter, R. (2020). Extending drawings of graphs to arrangements of pseudolines. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">https://doi.org/10.4230/LIPIcs.SoCG.2020.9</a>","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements of Pseudolines.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.9\">10.4230/LIPIcs.SoCG.2020.9</a>.","ieee":"A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings of graphs to arrangements of pseudolines,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","ista":"Arroyo Guevara AM, Bensmail J, Bruce Richter R. 2020. Extending drawings of graphs to arrangements of pseudolines. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 9:1-9:14."},"alternative_title":["LIPIcs"],"date_created":"2020-06-22T09:14:21Z","ec_funded":1,"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)"},"date_published":"2020-06-01T00:00:00Z","language":[{"iso":"eng"}],"publication":"36th International Symposium on Computational Geometry","scopus_import":"1","type":"conference","doi":"10.4230/LIPIcs.SoCG.2020.9","title":"Extending drawings of graphs to arrangements of pseudolines","arxiv":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771436"]},"article_number":"9:1 - 9:14","intvolume":"       164","year":"2020","corr_author":"1","quality_controlled":"1","publication_status":"published","has_accepted_license":"1","ddc":["510"],"author":[{"first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Bensmail, Julien","last_name":"Bensmail","first_name":"Julien"},{"first_name":"R.","last_name":"Bruce Richter","full_name":"Bruce Richter, R."}],"_id":"7994","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","conference":{"end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"file_date_updated":"2020-07-14T12:48:06Z","oa":1,"date_updated":"2025-07-10T11:54:58Z","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","external_id":{"arxiv":["1804.09317"]}},{"date_updated":"2025-07-10T11:57:06Z","day":"18","external_id":{"arxiv":["2007.02894"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020"}],"publication_status":"published","quality_controlled":"1","conference":{"name":"MFCS: Mathematical Foundations of Computer Science","start_date":"2020-08-24","location":"Prague, Czech Republic","end_date":"2020-08-28"},"oa":1,"file_date_updated":"2020-09-21T13:57:34Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"],"has_accepted_license":"1","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"first_name":"Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen"},{"first_name":"Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","full_name":"Jecker, Ismael R","last_name":"Jecker"},{"first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267","last_name":"Svoboda"}],"_id":"8533","doi":"10.4230/LIPIcs.MFCS.2020.22","type":"conference","publication":"45th International Symposium on Mathematical Foundations of Computer Science","date_published":"2020-08-18T00:00:00Z","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":"       170","year":"2020","acknowledgement":"Krishnendu Chatterjee: The research was partially supported by the Vienna Science and\r\nTechnology Fund (WWTF) Project ICT15-003.\r\nIsmaël Jecker: This project has received funding from the European Union’s Horizon 2020 research\r\nand innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411.","article_number":"22:1-22:13","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771597"]},"arxiv":1,"title":"Simplified game of life: Algorithms and complexity","status":"public","department":[{"_id":"KrCh"}],"month":"08","volume":170,"abstract":[{"lang":"eng","text":"Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp., overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e.g., configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete."}],"article_processing_charge":"No","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"ec_funded":1,"date_created":"2020-09-20T22:01:36Z","citation":{"ama":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Simplified game of life: Algorithms and complexity. In: <i>45th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">10.4230/LIPIcs.MFCS.2020.22</a>","short":"K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Simplified game of life: Algorithms and complexity,” in <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Prague, Czech Republic, 2020, vol. 170.","ista":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2020. Simplified game of life: Algorithms and complexity. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 22:1-22:13.","apa":"Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., &#38; Svoboda, J. (2020). Simplified game of life: Algorithms and complexity. In <i>45th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">https://doi.org/10.4230/LIPIcs.MFCS.2020.22</a>","mla":"Chatterjee, Krishnendu, et al. “Simplified Game of Life: Algorithms and Complexity.” <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 170, 22:1-22:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">10.4230/LIPIcs.MFCS.2020.22</a>.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub Svoboda. “Simplified Game of Life: Algorithms and Complexity.” In <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.22\">https://doi.org/10.4230/LIPIcs.MFCS.2020.22</a>."},"alternative_title":["LIPIcs"],"file":[{"success":1,"checksum":"bbd7c4f55d45f2ff2a0a4ef0e10a77b1","content_type":"application/pdf","file_name":"2020_LIPIcs_Chatterjee.pdf","date_updated":"2020-09-21T13:57:34Z","file_size":491374,"access_level":"open_access","creator":"dernst","date_created":"2020-09-21T13:57:34Z","relation":"main_file","file_id":"8550"}],"oa_version":"Published Version"},{"type":"conference","scopus_import":"1","language":[{"iso":"eng"}],"publication":"45th International Symposium on Mathematical Foundations of Computer Science","date_published":"2020-08-18T00:00:00Z","doi":"10.4230/LIPIcs.MFCS.2020.51","article_number":"51:1-51:12","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771597"]},"title":"Unary prime languages","year":"2020","intvolume":"       170","acknowledgement":"Ismaël Jecker: This project has received funding from the European Union’s Horizon\r\n2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.\r\n754411. Nicolas Mazzocchi: PhD fellowship FRIA from the F.R.S.-FNRS.","department":[{"_id":"KrCh"}],"article_processing_charge":"No","abstract":[{"lang":"eng","text":"A regular language L of finite words is composite if there are regular languages L₁,L₂,…,L_t such that L = ⋂_{i = 1}^t L_i and the index (number of states in a minimal DFA) of every language L_i is strictly smaller than the index of L. Otherwise, L is prime. Primality of regular languages was introduced and studied in [O. Kupferman and J. Mosheiff, 2015], where the complexity of deciding the primality of the language of a given DFA was left open, with a doubly-exponential gap between the upper and lower bounds. We study primality for unary regular languages, namely regular languages with a singleton alphabet. A unary language corresponds to a subset of ℕ, making the study of unary prime languages closer to that of primality in number theory. We show that the setting of languages is richer. In particular, while every composite number is the product of two smaller numbers, the number t of languages necessary to decompose a composite unary language induces a strict hierarchy. In addition, a primality witness for a unary language L, namely a word that is not in L but is in all products of languages that contain L and have an index smaller than L’s, may be of exponential length. Still, we are able to characterize compositionality by structural properties of a DFA for L, leading to a LogSpace algorithm for primality checking of unary DFAs."}],"volume":170,"month":"08","status":"public","alternative_title":["LIPIcs"],"citation":{"ista":"Jecker IR, Kupferman O, Mazzocchi N. 2020. Unary prime languages. 45th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 170, 51:1-51:12.","ieee":"I. R. Jecker, O. Kupferman, and N. Mazzocchi, “Unary prime languages,” in <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Prague, Czech Republic, 2020, vol. 170.","apa":"Jecker, I. R., Kupferman, O., &#38; Mazzocchi, N. (2020). Unary prime languages. In <i>45th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 170). Prague, Czech Republic: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">https://doi.org/10.4230/LIPIcs.MFCS.2020.51</a>","mla":"Jecker, Ismael R., et al. “Unary Prime Languages.” <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 170, 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">10.4230/LIPIcs.MFCS.2020.51</a>.","chicago":"Jecker, Ismael R, Orna Kupferman, and Nicolas Mazzocchi. “Unary Prime Languages.” In <i>45th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">https://doi.org/10.4230/LIPIcs.MFCS.2020.51</a>.","ama":"Jecker IR, Kupferman O, Mazzocchi N. Unary prime languages. In: <i>45th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 170. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2020.51\">10.4230/LIPIcs.MFCS.2020.51</a>","short":"I.R. Jecker, O. Kupferman, N. Mazzocchi, in:, 45th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"oa_version":"Published Version","file":[{"content_type":"application/pdf","file_size":597977,"file_name":"2020_LIPIcsMFCS_Jecker.pdf","date_updated":"2020-09-21T14:17:08Z","checksum":"2dc9e2fad6becd4563aef3e27a473f70","success":1,"file_id":"8552","creator":"dernst","date_created":"2020-09-21T14:17:08Z","relation":"main_file","access_level":"open_access"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"ec_funded":1,"date_created":"2020-09-20T22:01:36Z","date_updated":"2025-07-10T11:57:07Z","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"day":"18","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","quality_controlled":"1","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","first_name":"Ismael R","last_name":"Jecker","full_name":"Jecker, Ismael R"},{"first_name":"Orna","full_name":"Kupferman, Orna","last_name":"Kupferman"},{"first_name":"Nicolas","full_name":"Mazzocchi, Nicolas","last_name":"Mazzocchi"}],"_id":"8534","has_accepted_license":"1","ddc":["000"],"file_date_updated":"2020-09-21T14:17:08Z","oa":1,"conference":{"end_date":"2020-08-28","location":"Prague, Czech Republic","name":"MFCS: Mathematical Foundations of Computer Science","start_date":"2020-08-24"}},{"doi":"10.4230/LIPIcs.CONCUR.2020.2","type":"conference","language":[{"iso":"eng"}],"date_published":"2020-08-06T00:00:00Z","publication":"31st International Conference on Concurrency Theory","scopus_import":"1","intvolume":"       171","year":"2020","acknowledgement":"We would like to thank all our collaborators Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný, Josef Tkadlec, and Ðorđe Žikelić; we hope the collaboration was as fun and meaningful for you as it was for us.","publication_identifier":{"isbn":["9783959771603"],"issn":["1868-8969"]},"article_number":"2","title":"A survey of bidding games on graphs","status":"public","department":[{"_id":"ToHe"}],"volume":171,"month":"08","abstract":[{"lang":"eng","text":"A graph game is a two-player zero-sum game in which the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. In bidding games, both players have budgets, and in each turn, we hold an \"auction\" (bidding) to determine which player moves the token. In this survey, we consider several bidding mechanisms and study their effect on the properties of the game. Specifically, bidding games, and in particular bidding games of infinite duration, have an intriguing equivalence with random-turn games in which in each turn, the player who moves is chosen randomly. We show how minor changes in the bidding mechanism lead to unexpected differences in the equivalence with random-turn games."}],"article_processing_charge":"No","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"date_created":"2020-10-04T22:01:36Z","citation":{"ama":"Avni G, Henzinger TA. A survey of bidding games on graphs. In: <i>31st International Conference on Concurrency Theory</i>. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">10.4230/LIPIcs.CONCUR.2020.2</a>","short":"G. Avni, T.A. Henzinger, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"G. Avni and T. A. Henzinger, “A survey of bidding games on graphs,” in <i>31st International Conference on Concurrency Theory</i>, Virtual, 2020, vol. 171.","ista":"Avni G, Henzinger TA. 2020. A survey of bidding games on graphs. 31st International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 171, 2.","mla":"Avni, Guy, and Thomas A. Henzinger. “A Survey of Bidding Games on Graphs.” <i>31st International Conference on Concurrency Theory</i>, vol. 171, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">10.4230/LIPIcs.CONCUR.2020.2</a>.","apa":"Avni, G., &#38; Henzinger, T. A. (2020). A survey of bidding games on graphs. In <i>31st International Conference on Concurrency Theory</i> (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.2</a>","chicago":"Avni, Guy, and Thomas A Henzinger. “A Survey of Bidding Games on Graphs.” In <i>31st International Conference on Concurrency Theory</i>, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.2\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.2</a>."},"alternative_title":["LIPIcs"],"file":[{"access_level":"open_access","file_id":"8611","creator":"dernst","date_created":"2020-10-05T14:13:19Z","relation":"main_file","checksum":"8f33b098e73724e0ac817f764d8e1a2d","success":1,"content_type":"application/pdf","date_updated":"2020-10-05T14:13:19Z","file_name":"2020_LIPIcsCONCUR_Avni.pdf","file_size":868510}],"oa_version":"Published Version","date_updated":"2025-07-10T11:57:09Z","day":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF"}],"publication_status":"published","quality_controlled":"1","corr_author":"1","conference":{"location":"Virtual","end_date":"2020-09-04","name":"CONCUR: Conference on Concurrency Theory","start_date":"2020-09-01"},"oa":1,"file_date_updated":"2020-10-05T14:13:19Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"],"has_accepted_license":"1","_id":"8599","author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy","orcid":"0000-0001-5588-8287","last_name":"Avni","full_name":"Avni, Guy"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","orcid":"0000-0002-2985-7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}]},{"title":"Multi-dimensional long-run average problems for vector addition systems with states","article_number":"23","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771603"]},"arxiv":1,"intvolume":"       171","year":"2020","language":[{"iso":"eng"}],"publication":"31st International Conference on Concurrency Theory","date_published":"2020-08-06T00:00:00Z","scopus_import":"1","type":"conference","doi":"10.4230/LIPIcs.CONCUR.2020.23","file":[{"success":1,"checksum":"5039752f644c4b72b9361d21a5e31baf","file_name":"2020_LIPIcsCONCUR_Chatterjee.pdf","date_updated":"2020-10-05T14:04:25Z","file_size":601231,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2020-10-05T14:04:25Z","creator":"dernst","file_id":"8610"}],"oa_version":"Published Version","citation":{"ama":"Chatterjee K, Henzinger TA, Otop J. Multi-dimensional long-run average problems for vector addition systems with states. In: <i>31st International Conference on Concurrency Theory</i>. Vol 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">10.4230/LIPIcs.CONCUR.2020.23</a>","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, 31st International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Multi-dimensional long-run average problems for vector addition systems with states,” in <i>31st International Conference on Concurrency Theory</i>, Virtual, 2020, vol. 171.","ista":"Chatterjee K, Henzinger TA, Otop J. 2020. Multi-dimensional long-run average problems for vector addition systems with states. 31st International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 171, 23.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2020). Multi-dimensional long-run average problems for vector addition systems with states. In <i>31st International Conference on Concurrency Theory</i> (Vol. 171). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.23</a>","mla":"Chatterjee, Krishnendu, et al. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” <i>31st International Conference on Concurrency Theory</i>, vol. 171, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">10.4230/LIPIcs.CONCUR.2020.23</a>.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States.” In <i>31st International Conference on Concurrency Theory</i>, Vol. 171. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2020.23\">https://doi.org/10.4230/LIPIcs.CONCUR.2020.23</a>."},"alternative_title":["LIPIcs"],"date_created":"2020-10-04T22:01:36Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"month":"08","volume":171,"abstract":[{"lang":"eng","text":"A vector addition system with states (VASS) consists of a finite set of states and counters. A transition changes the current state to the next state, and every counter is either incremented, or decremented, or left unchanged. A state and value for each counter is a configuration; and a computation is an infinite sequence of configurations with transitions between successive configurations. A probabilistic VASS consists of a VASS along with a probability distribution over the transitions for each state. Qualitative properties such as state and configuration reachability have been widely studied for VASS. In this work we consider multi-dimensional long-run average objectives for VASS and probabilistic VASS. For a counter, the cost of a configuration is the value of the counter; and the long-run average value of a computation for the counter is the long-run average of the costs of the configurations in the computation. The multi-dimensional long-run average problem given a VASS and a threshold value for each counter, asks whether there is a computation such that for each counter the long-run average value for the counter does not exceed the respective threshold. For probabilistic VASS, instead of the existence of a computation, we consider whether the expected long-run average value for each counter does not exceed the respective threshold. Our main results are as follows: we show that the multi-dimensional long-run average problem (a) is NP-complete for integer-valued VASS; (b) is undecidable for natural-valued VASS (i.e., nonnegative counters); and (c) can be solved in polynomial time for probabilistic integer-valued VASS, and probabilistic natural-valued VASS when all computations are non-terminating."}],"article_processing_charge":"No","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"status":"public","project":[{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF"},{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","grant_number":"S11402-N23","call_identifier":"FWF"},{"name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"06","external_id":{"arxiv":["2007.08917"]},"date_updated":"2025-07-10T11:57:10Z","has_accepted_license":"1","ddc":["000"],"_id":"8600","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","last_name":"Henzinger","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Otop, Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","conference":{"start_date":"2020-09-01","name":"CONCUR: Conference on Concurrency Theory","end_date":"2020-09-04","location":"Virtual"},"file_date_updated":"2020-10-05T14:04:25Z","oa":1,"quality_controlled":"1","corr_author":"1","publication_status":"published"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"26","project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"date_updated":"2026-04-08T07:01:29Z","conference":{"start_date":"2020-09-07","name":"ESA: European Symposium on Algorithms","end_date":"2020-09-09","location":"Virtual, Online; Pisa, Italy"},"oa":1,"file_date_updated":"2020-10-27T14:31:52Z","has_accepted_license":"1","ddc":["000"],"author":[{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","first_name":"Georg F","full_name":"Osang, Georg F","last_name":"Osang","orcid":"0000-0002-8882-5116"},{"full_name":"Rouxel-Labbé, Mael","last_name":"Rouxel-Labbé","first_name":"Mael"},{"full_name":"Teillaud, Monique","last_name":"Teillaud","first_name":"Monique"}],"_id":"8703","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","corr_author":"1","quality_controlled":"1","intvolume":"       173","year":"2020","title":"Generalizing CGAL periodic Delaunay triangulations","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"article_number":"75","doi":"10.4230/LIPIcs.ESA.2020.75","language":[{"iso":"eng"}],"date_published":"2020-08-26T00:00:00Z","publication":"28th Annual European Symposium on Algorithms","scopus_import":"1","type":"conference","date_created":"2020-10-25T23:01:18Z","ec_funded":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"file":[{"access_level":"open_access","file_id":"8712","date_created":"2020-10-27T14:31:52Z","creator":"cziletti","relation":"main_file","checksum":"fe0f7c49a99ed870c671b911e10d5496","success":1,"content_type":"application/pdf","file_size":733291,"date_updated":"2020-10-27T14:31:52Z","file_name":"2020_LIPIcs_Osang.pdf"}],"oa_version":"Published Version","citation":{"chicago":"Osang, Georg F, Mael Rouxel-Labbé, and Monique Teillaud. “Generalizing CGAL Periodic Delaunay Triangulations.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>.","apa":"Osang, G. F., Rouxel-Labbé, M., &#38; Teillaud, M. (2020). Generalizing CGAL periodic Delaunay triangulations. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Virtual, Online; Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>","mla":"Osang, Georg F., et al. “Generalizing CGAL Periodic Delaunay Triangulations.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">10.4230/LIPIcs.ESA.2020.75</a>.","ista":"Osang GF, Rouxel-Labbé M, Teillaud M. 2020. Generalizing CGAL periodic Delaunay triangulations. 28th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 173, 75.","ieee":"G. F. Osang, M. Rouxel-Labbé, and M. Teillaud, “Generalizing CGAL periodic Delaunay triangulations,” in <i>28th Annual European Symposium on Algorithms</i>, Virtual, Online; Pisa, Italy, 2020, vol. 173.","short":"G.F. Osang, M. Rouxel-Labbé, M. Teillaud, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Osang GF, Rouxel-Labbé M, Teillaud M. Generalizing CGAL periodic Delaunay triangulations. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">10.4230/LIPIcs.ESA.2020.75</a>"},"alternative_title":["LIPIcs"],"related_material":{"record":[{"status":"public","id":"9056","relation":"dissertation_contains"}]},"status":"public","abstract":[{"text":"Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. ","lang":"eng"}],"month":"08","volume":173,"article_processing_charge":"No","department":[{"_id":"HeEd"}]}]