[{"page":"18-33","abstract":[{"text":"A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces.","lang":"eng"}],"date_updated":"2025-07-21T07:28:03Z","month":"01","type":"conference","oa_version":"Preprint","volume":14466,"date_created":"2024-01-28T23:01:43Z","acknowledgement":"This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035]. A preliminary version of this work has been presented at the 38th European Workshop on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper, which includes appendices but is otherwise identical, is available as a technical report [10].","year":"2024","_id":"14888","oa":1,"publication_status":"published","date_published":"2024-01-06T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2202.12175"}],"alternative_title":["LNCS"],"status":"public","external_id":{"arxiv":["2202.12175"]},"intvolume":"     14466","citation":{"ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. In: <i>31st International Symposium on Graph Drawing and Network Visualization</i>. Vol 14466. Springer Nature; 2024:18-33. doi:<a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">10.1007/978-3-031-49275-4_2</a>","apa":"De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., &#38; Rote, G. (2024). Removing popular faces in curve arrangements. In <i>31st International Symposium on Graph Drawing and Network Visualization</i> (Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">https://doi.org/10.1007/978-3-031-49275-4_2</a>","ista":"De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14466, 18–33.","mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” <i>31st International Symposium on Graph Drawing and Network Visualization</i>, vol. 14466, Springer Nature, 2024, pp. 18–33, doi:<a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">10.1007/978-3-031-49275-4_2</a>.","chicago":"De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve Arrangements.” In <i>31st International Symposium on Graph Drawing and Network Visualization</i>, 14466:18–33. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-49275-4_2\">https://doi.org/10.1007/978-3-031-49275-4_2</a>.","ieee":"P. De Nooijer <i>et al.</i>, “Removing popular faces in curve arrangements,” in <i>31st International Symposium on Graph Drawing and Network Visualization</i>, Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.","short":"P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 18–33."},"author":[{"first_name":"Phoebe","last_name":"De Nooijer","full_name":"De Nooijer, Phoebe"},{"full_name":"Terziadis, Soeren","last_name":"Terziadis","first_name":"Soeren"},{"full_name":"Weinberger, Alexandra","first_name":"Alexandra","last_name":"Weinberger"},{"orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","last_name":"Masárová","first_name":"Zuzana"},{"full_name":"Mchedlidze, Tamara","last_name":"Mchedlidze","first_name":"Tamara"},{"first_name":"Maarten","last_name":"Löffler","full_name":"Löffler, Maarten"},{"full_name":"Rote, Günter","last_name":"Rote","first_name":"Günter"}],"day":"06","title":"Removing popular faces in curve arrangements","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publication":"31st International Symposium on Graph Drawing and Network Visualization","article_processing_charge":"No","scopus_import":"1","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031492747"],"issn":["0302-9743"]},"doi":"10.1007/978-3-031-49275-4_2","quality_controlled":"1","project":[{"grant_number":"101087907","_id":"bdb2a702-d553-11ed-ba76-f12e3e5a3bc6","name":"A quantum hybrid of atoms and milligram-scale pendulums: towards gravitational quantum mechanics"}],"conference":{"start_date":"2023-09-20","location":"Isola delle Femmine, Palermo, Italy","name":"GD: Graph Drawing and Network Visualization","end_date":"2023-09-22"},"language":[{"iso":"eng"}]},{"author":[{"last_name":"Pach","first_name":"János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János"},{"last_name":"Saghafian","first_name":"Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824","full_name":"Saghafian, Morteza"},{"full_name":"Schnider, Patrick","last_name":"Schnider","first_name":"Patrick"}],"day":"01","arxiv":1,"title":"Decomposition of geometric graphs into star-forests","publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"publication":"31st International Symposium on Graph Drawing and Network Visualization","scopus_import":"1","article_processing_charge":"No","ec_funded":1,"publication_identifier":{"issn":["03029743"],"eissn":["16113349"],"isbn":["9783031492716"]},"doi":"10.1007/978-3-031-49272-3_23","quality_controlled":"1","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Alpha Shape Theory Extended","grant_number":"788183"},{"grant_number":"Z00342","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize"}],"conference":{"location":"Isola delle Femmine, Palermo, Italy","name":"GD: Graph Drawing and Network Visualization","start_date":"2023-09-20","end_date":"2023-09-22"},"language":[{"iso":"eng"}],"page":"339-346","type":"conference","oa_version":"Preprint","month":"01","abstract":[{"text":"We solve a problem of Dujmović and Wood (2007) by showing that a complete convex geometric graph on n vertices cannot be decomposed into fewer than n-1 star-forests, each consisting of noncrossing edges. This bound is clearly tight. We also discuss similar questions for abstract graphs.","lang":"eng"}],"date_updated":"2024-02-20T09:13:07Z","volume":14465,"date_created":"2024-02-18T23:01:03Z","acknowledgement":"János Pach’s Research partially supported by European Research Council (ERC), grant “GeoScape” No. 882971 and by the Hungarian Science Foundation (NKFIH), grant K-131529. Work by Morteza Saghafian is partially supported by the European Research Council (ERC), grant No. 788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant No. Z 342-N31.","year":"2024","_id":"15012","oa":1,"publication_status":"published","date_published":"2024-01-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2306.13201"}],"alternative_title":["LNCS"],"external_id":{"arxiv":["2306.13201"]},"status":"public","intvolume":"     14465","citation":{"chicago":"Pach, János, Morteza Saghafian, and Patrick Schnider. “Decomposition of Geometric Graphs into Star-Forests.” In <i>31st International Symposium on Graph Drawing and Network Visualization</i>, 14465:339–46. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-49272-3_23\">https://doi.org/10.1007/978-3-031-49272-3_23</a>.","ieee":"J. Pach, M. Saghafian, and P. Schnider, “Decomposition of geometric graphs into star-forests,” in <i>31st International Symposium on Graph Drawing and Network Visualization</i>, Isola delle Femmine, Palermo, Italy, 2024, vol. 14465, pp. 339–346.","short":"J. Pach, M. Saghafian, P. Schnider, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 339–346.","ama":"Pach J, Saghafian M, Schnider P. Decomposition of geometric graphs into star-forests. In: <i>31st International Symposium on Graph Drawing and Network Visualization</i>. Vol 14465. Springer Nature; 2024:339-346. doi:<a href=\"https://doi.org/10.1007/978-3-031-49272-3_23\">10.1007/978-3-031-49272-3_23</a>","apa":"Pach, J., Saghafian, M., &#38; Schnider, P. (2024). Decomposition of geometric graphs into star-forests. In <i>31st International Symposium on Graph Drawing and Network Visualization</i> (Vol. 14465, pp. 339–346). Isola delle Femmine, Palermo, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-49272-3_23\">https://doi.org/10.1007/978-3-031-49272-3_23</a>","ista":"Pach J, Saghafian M, Schnider P. 2024. Decomposition of geometric graphs into star-forests. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14465, 339–346.","mla":"Pach, János, et al. “Decomposition of Geometric Graphs into Star-Forests.” <i>31st International Symposium on Graph Drawing and Network Visualization</i>, vol. 14465, Springer Nature, 2024, pp. 339–46, doi:<a href=\"https://doi.org/10.1007/978-3-031-49272-3_23\">10.1007/978-3-031-49272-3_23</a>."}},{"citation":{"ama":"Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. On angles in higher order Brillouin tessellations and related tilings in the plane. <i>Discrete and Computational Geometry</i>. 2023. doi:<a href=\"https://doi.org/10.1007/s00454-023-00566-1\">10.1007/s00454-023-00566-1</a>","mla":"Edelsbrunner, Herbert, et al. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” <i>Discrete and Computational Geometry</i>, Springer Nature, 2023, doi:<a href=\"https://doi.org/10.1007/s00454-023-00566-1\">10.1007/s00454-023-00566-1</a>.","ista":"Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2023. On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry.","apa":"Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., &#38; Saghafian, M. (2023). On angles in higher order Brillouin tessellations and related tilings in the plane. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00566-1\">https://doi.org/10.1007/s00454-023-00566-1</a>","ieee":"H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, and M. Saghafian, “On angles in higher order Brillouin tessellations and related tilings in the plane,” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023.","chicago":"Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafari, Teresa Heiss, and Morteza Saghafian. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-023-00566-1\">https://doi.org/10.1007/s00454-023-00566-1</a>.","short":"H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, Discrete and Computational Geometry (2023)."},"external_id":{"arxiv":["2204.01076"],"isi":["001060727600004"]},"status":"public","date_published":"2023-09-07T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00454-023-00566-1"}],"oa":1,"publication_status":"epub_ahead","_id":"14345","acknowledgement":"Work by all authors but A. Garber is supported by the European Research Council (ERC), Grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), Grant No. I 02979-N35. Work by A. Garber is partially supported by the Alexander von Humboldt Foundation.","year":"2023","date_created":"2023-09-17T22:01:10Z","abstract":[{"text":"For a locally finite set in R2, the order-k Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in k. As an example, a stationary Poisson point process in R2  is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. 6, 85–127 (1970)).","lang":"eng"}],"date_updated":"2023-12-13T12:25:06Z","oa_version":"Published Version","type":"journal_article","month":"09","isi":1,"language":[{"iso":"eng"}],"project":[{"name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"788183"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"I02979-N35","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes"}],"doi":"10.1007/s00454-023-00566-1","quality_controlled":"1","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publication":"Discrete and Computational Geometry","article_processing_charge":"Yes (via OA deal)","ec_funded":1,"scopus_import":"1","article_type":"original","publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"arxiv":1,"title":"On angles in higher order Brillouin tessellations and related tilings in the plane","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"first_name":"Alexey","last_name":"Garber","full_name":"Garber, Alexey"},{"last_name":"Ghafari","first_name":"Mohadese","full_name":"Ghafari, Mohadese"},{"first_name":"Teresa","last_name":"Heiss","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1780-2689","full_name":"Heiss, Teresa"},{"last_name":"Saghafian","first_name":"Morteza","full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824"}],"day":"07"},{"citation":{"short":"I. Castellano, A. Giordano Bruno, N. Zava, Theoretical Computer Science 977 (2023).","ieee":"I. Castellano, A. Giordano Bruno, and N. Zava, “Weakly weighted generalised quasi-metric spaces and semilattices,” <i>Theoretical Computer Science</i>, vol. 977. Elsevier, 2023.","chicago":"Castellano, Ilaria, Anna Giordano Bruno, and Nicolò Zava. “Weakly Weighted Generalised Quasi-Metric Spaces and Semilattices.” <i>Theoretical Computer Science</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.tcs.2023.114129\">https://doi.org/10.1016/j.tcs.2023.114129</a>.","mla":"Castellano, Ilaria, et al. “Weakly Weighted Generalised Quasi-Metric Spaces and Semilattices.” <i>Theoretical Computer Science</i>, vol. 977, 114129, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114129\">10.1016/j.tcs.2023.114129</a>.","ista":"Castellano I, Giordano Bruno A, Zava N. 2023. Weakly weighted generalised quasi-metric spaces and semilattices. Theoretical Computer Science. 977, 114129.","apa":"Castellano, I., Giordano Bruno, A., &#38; Zava, N. (2023). Weakly weighted generalised quasi-metric spaces and semilattices. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.114129\">https://doi.org/10.1016/j.tcs.2023.114129</a>","ama":"Castellano I, Giordano Bruno A, Zava N. Weakly weighted generalised quasi-metric spaces and semilattices. <i>Theoretical Computer Science</i>. 2023;977. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114129\">10.1016/j.tcs.2023.114129</a>"},"intvolume":"       977","status":"public","external_id":{"arxiv":["2212.08424"],"isi":["001076934000001"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2212.08424 "}],"date_published":"2023-10-25T00:00:00Z","publication_status":"published","oa":1,"_id":"14362","year":"2023","date_created":"2023-09-24T22:01:11Z","volume":977,"month":"10","type":"journal_article","oa_version":"Preprint","date_updated":"2024-01-30T13:22:04Z","abstract":[{"text":"Motivated by recent applications to entropy theory in dynamical systems, we generalise notions introduced by Matthews and define weakly weighted and componentwise weakly weighted (generalised) quasi-metrics. We then systematise and extend to full generality the correspondences between these objects and other structures arising in theoretical computer science and dynamics. In particular, we study the correspondences with weak partial metrics and, if the underlying space is a semilattice, with invariant (generalised) quasi-metrics satisfying the descending path condition, and with strictly monotone semi(-co-)valuations.\r\nWe conclude discussing, for endomorphisms of generalised quasi-metric semilattices, a generalisation of both the known intrinsic semilattice entropy and the semigroup entropy.","lang":"eng"}],"language":[{"iso":"eng"}],"isi":1,"quality_controlled":"1","doi":"10.1016/j.tcs.2023.114129","publication_identifier":{"issn":["0304-3975"]},"article_type":"original","scopus_import":"1","article_processing_charge":"No","publication":"Theoretical Computer Science","department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Elsevier","article_number":"114129","title":"Weakly weighted generalised quasi-metric spaces and semilattices","arxiv":1,"day":"25","author":[{"first_name":"Ilaria","last_name":"Castellano","full_name":"Castellano, Ilaria"},{"last_name":"Giordano Bruno","first_name":"Anna","full_name":"Giordano Bruno, Anna"},{"last_name":"Zava","first_name":"Nicolò","full_name":"Zava, Nicolò","id":"c8b3499c-7a77-11eb-b046-aa368cbbf2ad","orcid":"0000-0001-8686-1888"}]},{"department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"World Scientific Publishing","article_processing_charge":"No","scopus_import":"1","article_type":"original","publication":"International Journal of Foundations of Computer Science","day":"05","author":[{"full_name":"Ambrus, Áron","first_name":"Áron","last_name":"Ambrus"},{"first_name":"Mónika","last_name":"Csikós","full_name":"Csikós, Mónika"},{"last_name":"Kiss","first_name":"Gergely","full_name":"Kiss, Gergely"},{"first_name":"János","last_name":"Pach","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János"},{"last_name":"Somlai","first_name":"Gábor","full_name":"Somlai, Gábor"}],"arxiv":1,"title":"Optimal embedded and enclosing isosceles triangles","language":[{"iso":"eng"}],"issue":"7","isi":1,"publication_identifier":{"issn":["0129-0541"],"eissn":["1793-6373"]},"quality_controlled":"1","doi":"10.1142/S012905412342008X","year":"2023","_id":"14464","date_updated":"2023-12-13T13:04:55Z","abstract":[{"lang":"eng","text":"Given a triangle Δ, we study the problem of determining the smallest enclosing and largest embedded isosceles triangles of Δ with respect to area and perimeter. This problem was initially posed by Nandakumar [17, 22] and was first studied by Kiss, Pach, and Somlai [13], who showed that if Δ′ is the smallest area isosceles triangle containing Δ, then Δ′ and Δ share a side and an angle. In the present paper, we prove that for any triangle Δ, every maximum area isosceles triangle embedded in Δ and every maximum perimeter isosceles triangle embedded in Δ shares a side and an angle with Δ. Somewhat surprisingly, the case of minimum perimeter enclosing triangles is different: there are infinite families of triangles Δ whose minimum perimeter isosceles containers do not share a side and an angle with Δ."}],"month":"10","oa_version":"Preprint","type":"journal_article","page":"737-760","date_created":"2023-10-29T23:01:18Z","volume":34,"external_id":{"isi":["001080874400001"],"arxiv":["2205.11637"]},"status":"public","citation":{"ieee":"Á. Ambrus, M. Csikós, G. Kiss, J. Pach, and G. Somlai, “Optimal embedded and enclosing isosceles triangles,” <i>International Journal of Foundations of Computer Science</i>, vol. 34, no. 7. World Scientific Publishing, pp. 737–760, 2023.","chicago":"Ambrus, Áron, Mónika Csikós, Gergely Kiss, János Pach, and Gábor Somlai. “Optimal Embedded and Enclosing Isosceles Triangles.” <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing, 2023. <a href=\"https://doi.org/10.1142/S012905412342008X\">https://doi.org/10.1142/S012905412342008X</a>.","short":"Á. Ambrus, M. Csikós, G. Kiss, J. Pach, G. Somlai, International Journal of Foundations of Computer Science 34 (2023) 737–760.","ama":"Ambrus Á, Csikós M, Kiss G, Pach J, Somlai G. Optimal embedded and enclosing isosceles triangles. <i>International Journal of Foundations of Computer Science</i>. 2023;34(7):737-760. doi:<a href=\"https://doi.org/10.1142/S012905412342008X\">10.1142/S012905412342008X</a>","ista":"Ambrus Á, Csikós M, Kiss G, Pach J, Somlai G. 2023. Optimal embedded and enclosing isosceles triangles. International Journal of Foundations of Computer Science. 34(7), 737–760.","mla":"Ambrus, Áron, et al. “Optimal Embedded and Enclosing Isosceles Triangles.” <i>International Journal of Foundations of Computer Science</i>, vol. 34, no. 7, World Scientific Publishing, 2023, pp. 737–60, doi:<a href=\"https://doi.org/10.1142/S012905412342008X\">10.1142/S012905412342008X</a>.","apa":"Ambrus, Á., Csikós, M., Kiss, G., Pach, J., &#38; Somlai, G. (2023). Optimal embedded and enclosing isosceles triangles. <i>International Journal of Foundations of Computer Science</i>. World Scientific Publishing. <a href=\"https://doi.org/10.1142/S012905412342008X\">https://doi.org/10.1142/S012905412342008X</a>"},"intvolume":"        34","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2205.11637"}],"date_published":"2023-10-05T00:00:00Z"},{"page":"191-221","abstract":[{"lang":"eng","text":"Motivated by a problem posed in [10], we investigate the closure operators of the category SLatt of join semilattices and its subcategory SLattO of join semilattices with bottom element. In particular, we show that there are only finitely many closure operators of both categories, and provide a complete classification. We use this result to deduce the known fact that epimorphisms of SLatt and SLattO are surjective. We complement the paper with two different proofs of this result using either generators or Isbell’s zigzag theorem."}],"date_updated":"2023-11-20T09:24:48Z","oa_version":"None","type":"journal_article","month":"11","volume":46,"date_created":"2023-11-19T23:00:55Z","acknowledgement":"The first and second named authors are members of GNSAGA – INdAM.\r\nThe third named author was supported by the FWF Grant, Project number I4245–N35","year":"2023","_id":"14557","publication_status":"published","date_published":"2023-11-01T00:00:00Z","status":"public","intvolume":"        46","citation":{"chicago":"Dikranjan, D., A. Giordano Bruno, and Nicolò Zava. “Epimorphisms and Closure Operators of Categories of Semilattices.” <i>Quaestiones Mathematicae</i>. Taylor &#38; Francis, 2023. <a href=\"https://doi.org/10.2989/16073606.2023.2247731\">https://doi.org/10.2989/16073606.2023.2247731</a>.","ieee":"D. Dikranjan, A. Giordano Bruno, and N. Zava, “Epimorphisms and closure operators of categories of semilattices,” <i>Quaestiones Mathematicae</i>, vol. 46, no. S1. Taylor &#38; Francis, pp. 191–221, 2023.","short":"D. Dikranjan, A. Giordano Bruno, N. Zava, Quaestiones Mathematicae 46 (2023) 191–221.","ama":"Dikranjan D, Giordano Bruno A, Zava N. Epimorphisms and closure operators of categories of semilattices. <i>Quaestiones Mathematicae</i>. 2023;46(S1):191-221. doi:<a href=\"https://doi.org/10.2989/16073606.2023.2247731\">10.2989/16073606.2023.2247731</a>","apa":"Dikranjan, D., Giordano Bruno, A., &#38; Zava, N. (2023). Epimorphisms and closure operators of categories of semilattices. <i>Quaestiones Mathematicae</i>. Taylor &#38; Francis. <a href=\"https://doi.org/10.2989/16073606.2023.2247731\">https://doi.org/10.2989/16073606.2023.2247731</a>","mla":"Dikranjan, D., et al. “Epimorphisms and Closure Operators of Categories of Semilattices.” <i>Quaestiones Mathematicae</i>, vol. 46, no. S1, Taylor &#38; Francis, 2023, pp. 191–221, doi:<a href=\"https://doi.org/10.2989/16073606.2023.2247731\">10.2989/16073606.2023.2247731</a>.","ista":"Dikranjan D, Giordano Bruno A, Zava N. 2023. Epimorphisms and closure operators of categories of semilattices. Quaestiones Mathematicae. 46(S1), 191–221."},"author":[{"first_name":"D.","last_name":"Dikranjan","full_name":"Dikranjan, D."},{"full_name":"Giordano Bruno, A.","last_name":"Giordano Bruno","first_name":"A."},{"orcid":"0000-0001-8686-1888","id":"c8b3499c-7a77-11eb-b046-aa368cbbf2ad","full_name":"Zava, Nicolò","last_name":"Zava","first_name":"Nicolò"}],"day":"01","title":"Epimorphisms and closure operators of categories of semilattices","publisher":"Taylor & Francis","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"publication":"Quaestiones Mathematicae","article_processing_charge":"No","scopus_import":"1","article_type":"original","publication_identifier":{"issn":["1607-3606"],"eissn":["1727-933X"]},"doi":"10.2989/16073606.2023.2247731","quality_controlled":"1","project":[{"name":"Algebraic Footprints of Geometric Features in Homology","call_identifier":"FWF","_id":"26AD5D90-B435-11E9-9278-68D0E5697425","grant_number":"I04245"}],"language":[{"iso":"eng"}],"issue":"S1"},{"date_created":"2024-01-08T09:59:46Z","file_date_updated":"2024-01-08T10:09:14Z","volume":45,"oa_version":"Published Version","type":"journal_article","month":"12","abstract":[{"lang":"eng","text":"Attempts to incorporate topological information in supervised learning tasks have resulted in the creation of several techniques for vectorizing persistent homology barcodes. In this paper, we study thirteen such methods. Besides describing an organizational framework for these methods, we comprehensively benchmark them against three well-known classification tasks. Surprisingly, we discover that the best-performing method is a simple vectorization, which consists only of a few elementary summary statistics. Finally, we provide a convenient web application which has been designed to facilitate exploration and experimentation with various vectorization methods."}],"date_updated":"2024-01-08T10:11:46Z","page":"14069-14080","_id":"14739","year":"2023","acknowledgement":"The work of Maria-Jose Jimenez, Eduardo Paluzo-Hidalgo and Manuel Soriano-Trigueros was supported in part by the Spanish grant Ministerio de Ciencia e Innovacion under Grants TED2021-129438B-I00 and PID2019-107339GB-I00, and in part by REXASI-PRO H-EU project, call HORIZON-CL4-2021-HUMAN-01-01 under Grant 101070028. The work of\r\nMaria-Jose Jimenez was supported by a grant of Convocatoria de la Universidad de Sevilla para la recualificacion del sistema universitario español, 2021-23, funded by the European Union, NextGenerationEU. The work of Vidit Nanda was supported in part by EPSRC under Grant EP/R018472/1 and in part by US AFOSR under Grant FA9550-22-1-0462. \r\nWe are grateful to the team of GUDHI and TEASPOON developers, for their work and their support. We are also grateful to Streamlit for providing extra resources to deploy the web app\r\nonline on Streamlit community cloud. We thank the anonymous referees for their helpful suggestions.","date_published":"2023-12-01T00:00:00Z","ddc":["000"],"has_accepted_license":"1","publication_status":"published","oa":1,"citation":{"short":"D. Ali, A. Asaad, M.-J. Jimenez, V. Nanda, E. Paluzo-Hidalgo, M. Soriano Trigueros, IEEE Transactions on Pattern Analysis and Machine Intelligence 45 (2023) 14069–14080.","ieee":"D. Ali, A. Asaad, M.-J. Jimenez, V. Nanda, E. Paluzo-Hidalgo, and M. Soriano Trigueros, “A survey of vectorization methods in topological data analysis,” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>, vol. 45, no. 12. IEEE, pp. 14069–14080, 2023.","chicago":"Ali, Dashti, Aras Asaad, Maria-Jose Jimenez, Vidit Nanda, Eduardo Paluzo-Hidalgo, and Manuel Soriano Trigueros. “A Survey of Vectorization Methods in Topological Data Analysis.” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. IEEE, 2023. <a href=\"https://doi.org/10.1109/tpami.2023.3308391\">https://doi.org/10.1109/tpami.2023.3308391</a>.","mla":"Ali, Dashti, et al. “A Survey of Vectorization Methods in Topological Data Analysis.” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>, vol. 45, no. 12, IEEE, 2023, pp. 14069–80, doi:<a href=\"https://doi.org/10.1109/tpami.2023.3308391\">10.1109/tpami.2023.3308391</a>.","ista":"Ali D, Asaad A, Jimenez M-J, Nanda V, Paluzo-Hidalgo E, Soriano Trigueros M. 2023. A survey of vectorization methods in topological data analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence. 45(12), 14069–14080.","apa":"Ali, D., Asaad, A., Jimenez, M.-J., Nanda, V., Paluzo-Hidalgo, E., &#38; Soriano Trigueros, M. (2023). A survey of vectorization methods in topological data analysis. <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. IEEE. <a href=\"https://doi.org/10.1109/tpami.2023.3308391\">https://doi.org/10.1109/tpami.2023.3308391</a>","ama":"Ali D, Asaad A, Jimenez M-J, Nanda V, Paluzo-Hidalgo E, Soriano Trigueros M. A survey of vectorization methods in topological data analysis. <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. 2023;45(12):14069-14080. doi:<a href=\"https://doi.org/10.1109/tpami.2023.3308391\">10.1109/tpami.2023.3308391</a>"},"intvolume":"        45","status":"public","title":"A survey of vectorization methods in topological data analysis","file":[{"date_created":"2024-01-08T10:09:14Z","access_level":"open_access","file_id":"14740","date_updated":"2024-01-08T10:09:14Z","checksum":"465c28ef0b151b4b1fb47977ed5581ab","file_size":2370988,"content_type":"application/pdf","relation":"main_file","creator":"dernst","file_name":"2023_IEEEToP_Ali.pdf","success":1}],"day":"01","author":[{"full_name":"Ali, Dashti","first_name":"Dashti","last_name":"Ali"},{"first_name":"Aras","last_name":"Asaad","full_name":"Asaad, Aras"},{"first_name":"Maria-Jose","last_name":"Jimenez","full_name":"Jimenez, Maria-Jose"},{"full_name":"Nanda, Vidit","first_name":"Vidit","last_name":"Nanda"},{"last_name":"Paluzo-Hidalgo","first_name":"Eduardo","full_name":"Paluzo-Hidalgo, Eduardo"},{"last_name":"Soriano Trigueros","first_name":"Manuel","orcid":"0000-0003-2449-1433","id":"15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8","full_name":"Soriano Trigueros, Manuel"}],"article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_processing_charge":"Yes (in subscription journal)","publication":"IEEE Transactions on Pattern Analysis and Machine Intelligence","department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IEEE","quality_controlled":"1","doi":"10.1109/tpami.2023.3308391","publication_identifier":{"eissn":["1939-3539"],"issn":["0162-8828"]},"issue":"12","language":[{"iso":"eng"}],"keyword":["Applied Mathematics","Artificial Intelligence","Computational Theory and Mathematics","Computer Vision and Pattern Recognition","Software"]},{"external_id":{"isi":["001013526000001"]},"status":"public","citation":{"ama":"Čomić L, Largeteau-Skapin G, Zrour R, Biswas R, Andres E. Discrete analytical objects in the body-centered cubic grid. <i>Pattern Recognition</i>. 2023;142(10). doi:<a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">10.1016/j.patcog.2023.109693</a>","mla":"Čomić, Lidija, et al. “Discrete Analytical Objects in the Body-Centered Cubic Grid.” <i>Pattern Recognition</i>, vol. 142, no. 10, 109693, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">10.1016/j.patcog.2023.109693</a>.","ista":"Čomić L, Largeteau-Skapin G, Zrour R, Biswas R, Andres E. 2023. Discrete analytical objects in the body-centered cubic grid. Pattern Recognition. 142(10), 109693.","apa":"Čomić, L., Largeteau-Skapin, G., Zrour, R., Biswas, R., &#38; Andres, E. (2023). Discrete analytical objects in the body-centered cubic grid. <i>Pattern Recognition</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">https://doi.org/10.1016/j.patcog.2023.109693</a>","ieee":"L. Čomić, G. Largeteau-Skapin, R. Zrour, R. Biswas, and E. Andres, “Discrete analytical objects in the body-centered cubic grid,” <i>Pattern Recognition</i>, vol. 142, no. 10. Elsevier, 2023.","chicago":"Čomić, Lidija, Gaëlle Largeteau-Skapin, Rita Zrour, Ranita Biswas, and Eric Andres. “Discrete Analytical Objects in the Body-Centered Cubic Grid.” <i>Pattern Recognition</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.patcog.2023.109693\">https://doi.org/10.1016/j.patcog.2023.109693</a>.","short":"L. Čomić, G. Largeteau-Skapin, R. Zrour, R. Biswas, E. Andres, Pattern Recognition 142 (2023)."},"intvolume":"       142","publication_status":"published","date_published":"2023-10-01T00:00:00Z","year":"2023","acknowledgement":"The first author has been partially supported by the Ministry of Science, Technological Development and Innovation of the Republic of Serbia through the project no. 451-03-47/2023-01/200156. The fourth author is funded by the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), grant no. I 02979-N35.","_id":"13134","abstract":[{"lang":"eng","text":"We propose a characterization of discrete analytical spheres, planes and lines in the body-centered cubic (BCC) grid, both in the Cartesian and in the recently proposed alternative compact coordinate system, in which each integer triplet addresses some voxel in the grid. We define spheres and planes through double Diophantine inequalities and investigate their relevant topological features, such as functionality or the interrelation between the thickness of the objects and their connectivity and separation properties. We define lines as the intersection of planes. The number of the planes (up to six) is equal to the number of the pairs of faces of a BCC voxel that are parallel to the line."}],"date_updated":"2023-10-10T07:37:16Z","oa_version":"None","month":"10","type":"journal_article","date_created":"2023-06-18T22:00:45Z","volume":142,"project":[{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Persistence and stability of geometric complexes","grant_number":"I02979-N35"},{"grant_number":"I4887","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","name":"Discretization in Geometry and Dynamics"}],"language":[{"iso":"eng"}],"issue":"10","isi":1,"publication_identifier":{"issn":["0031-3203"]},"quality_controlled":"1","doi":"10.1016/j.patcog.2023.109693","department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Elsevier","scopus_import":"1","article_processing_charge":"No","article_type":"original","publication":"Pattern Recognition","day":"01","author":[{"full_name":"Čomić, Lidija","last_name":"Čomić","first_name":"Lidija"},{"last_name":"Largeteau-Skapin","first_name":"Gaëlle","full_name":"Largeteau-Skapin, Gaëlle"},{"first_name":"Rita","last_name":"Zrour","full_name":"Zrour, Rita"},{"first_name":"Ranita","last_name":"Biswas","full_name":"Biswas, Ranita","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5372-7890"},{"full_name":"Andres, Eric","first_name":"Eric","last_name":"Andres"}],"title":"Discrete analytical objects in the body-centered cubic grid","article_number":"109693"},{"publication_identifier":{"eissn":["1096-0899"],"issn":["0097-3165"]},"quality_controlled":"1","doi":"10.1016/j.jcta.2023.105776","issue":"10","language":[{"iso":"eng"}],"day":"01","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","file":[{"success":1,"file_name":"2023_JourCombinatiorialTheory_Fang.pdf","creator":"dernst","relation":"main_file","content_type":"application/pdf","file_size":352555,"checksum":"9eebc213b4182a66063a99083ff5bd04","date_updated":"2024-01-30T12:03:10Z","file_id":"14902","access_level":"open_access","date_created":"2024-01-30T12:03:10Z"}],"author":[{"full_name":"Fang, Lixing","first_name":"Lixing","last_name":"Fang"},{"first_name":"Hao","last_name":"Huang","full_name":"Huang, Hao"},{"last_name":"Pach","first_name":"János","full_name":"Pach, János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4"},{"full_name":"Tardos, Gábor","last_name":"Tardos","first_name":"Gábor"},{"first_name":"Junchi","last_name":"Zuo","full_name":"Zuo, Junchi"}],"article_number":"105776","arxiv":1,"title":"Successive vertex orderings of fully regular graphs","department":[{"_id":"HeEd"}],"publisher":"Elsevier","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","short":"CC BY-NC-SA (4.0)"},"article_type":"original","article_processing_charge":"Yes (in subscription journal)","scopus_import":"1","publication":"Journal of Combinatorial Theory. Series A","has_accepted_license":"1","oa":1,"publication_status":"published","date_published":"2023-10-01T00:00:00Z","ddc":["510"],"status":"public","external_id":{"arxiv":["2206.13592"]},"citation":{"chicago":"Fang, Lixing, Hao Huang, János Pach, Gábor Tardos, and Junchi Zuo. “Successive Vertex Orderings of Fully Regular Graphs.” <i>Journal of Combinatorial Theory. Series A</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">https://doi.org/10.1016/j.jcta.2023.105776</a>.","ieee":"L. Fang, H. Huang, J. Pach, G. Tardos, and J. Zuo, “Successive vertex orderings of fully regular graphs,” <i>Journal of Combinatorial Theory. Series A</i>, vol. 199, no. 10. Elsevier, 2023.","short":"L. Fang, H. Huang, J. Pach, G. Tardos, J. Zuo, Journal of Combinatorial Theory. Series A 199 (2023).","ama":"Fang L, Huang H, Pach J, Tardos G, Zuo J. Successive vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory Series A</i>. 2023;199(10). doi:<a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">10.1016/j.jcta.2023.105776</a>","apa":"Fang, L., Huang, H., Pach, J., Tardos, G., &#38; Zuo, J. (2023). Successive vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory. Series A</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">https://doi.org/10.1016/j.jcta.2023.105776</a>","ista":"Fang L, Huang H, Pach J, Tardos G, Zuo J. 2023. Successive vertex orderings of fully regular graphs. Journal of Combinatorial Theory. Series A. 199(10), 105776.","mla":"Fang, Lixing, et al. “Successive Vertex Orderings of Fully Regular Graphs.” <i>Journal of Combinatorial Theory. Series A</i>, vol. 199, no. 10, 105776, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.jcta.2023.105776\">10.1016/j.jcta.2023.105776</a>."},"intvolume":"       199","month":"10","type":"journal_article","oa_version":"Published Version","date_updated":"2024-01-30T12:03:51Z","abstract":[{"lang":"eng","text":"A graph G=(V, E) is called fully regular if for every independent set I c V, the number of vertices in V\\I  that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph.\r\nAs an application of our results, we give alternative proofs of two theorems of Stanley and Gao & Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph.\r\nAs another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small."}],"date_created":"2023-06-25T22:00:45Z","file_date_updated":"2024-01-30T12:03:10Z","volume":199,"year":"2023","_id":"13165"},{"author":[{"last_name":"Biswas","first_name":"Ranita","orcid":"0000-0002-5372-7890","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","full_name":"Biswas, Ranita"},{"last_name":"Cultrera Di Montesano","first_name":"Sebastiano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6249-0832","full_name":"Cultrera Di Montesano, Sebastiano"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824","first_name":"Morteza","last_name":"Saghafian"}],"day":"17","file":[{"file_name":"2023_Journal of Applied and Computational Topology_Biswas.pdf","success":1,"file_size":487355,"content_type":"application/pdf","relation":"main_file","creator":"alisjak","file_id":"13185","date_updated":"2023-07-03T09:41:05Z","checksum":"697249d5d1c61dea4410b9f021b70fce","date_created":"2023-07-03T09:41:05Z","access_level":"open_access"}],"title":"Geometric characterization of the persistence of 1D maps","publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"publication":"Journal of Applied and Computational Topology","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"scopus_import":"1","ec_funded":1,"article_processing_charge":"Yes (via OA deal)","publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"doi":"10.1007/s41468-023-00126-9","quality_controlled":"1","project":[{"grant_number":"788183","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended"},{"name":"Discretization in Geometry and Dynamics","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","grant_number":"I4887"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"month":"06","type":"journal_article","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We characterize critical points of 1-dimensional maps paired in persistent homology\r\ngeometrically and this way get elementary proofs of theorems about the symmetry\r\nof persistence diagrams and the variation of such maps. In particular, we identify\r\nbranching points and endpoints of networks as the sole source of asymmetry and\r\nrelate the cycle basis in persistent homology with a version of the stable marriage\r\nproblem. Our analysis provides the foundations of fast algorithms for maintaining a\r\ncollection of sorted lists together with its persistence diagram."}],"date_updated":"2023-10-18T08:13:10Z","file_date_updated":"2023-07-03T09:41:05Z","date_created":"2023-07-02T22:00:44Z","acknowledgement":"Open access funding provided by Austrian Science Fund (FWF). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35. The authors of this paper thank anonymous reviewers for their constructive criticism and Monika Henzinger for detailed comments on an earlier version of this paper.","year":"2023","_id":"13182","publication_status":"epub_ahead","oa":1,"has_accepted_license":"1","date_published":"2023-06-17T00:00:00Z","ddc":["000"],"status":"public","citation":{"apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., &#38; Saghafian, M. (2023). Geometric characterization of the persistence of 1D maps. <i>Journal of Applied and Computational Topology</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s41468-023-00126-9\">https://doi.org/10.1007/s41468-023-00126-9</a>","mla":"Biswas, Ranita, et al. “Geometric Characterization of the Persistence of 1D Maps.” <i>Journal of Applied and Computational Topology</i>, Springer Nature, 2023, doi:<a href=\"https://doi.org/10.1007/s41468-023-00126-9\">10.1007/s41468-023-00126-9</a>.","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2023. Geometric characterization of the persistence of 1D maps. Journal of Applied and Computational Topology.","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Geometric characterization of the persistence of 1D maps. <i>Journal of Applied and Computational Topology</i>. 2023. doi:<a href=\"https://doi.org/10.1007/s41468-023-00126-9\">10.1007/s41468-023-00126-9</a>","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Journal of Applied and Computational Topology (2023).","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Geometric Characterization of the Persistence of 1D Maps.” <i>Journal of Applied and Computational Topology</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s41468-023-00126-9\">https://doi.org/10.1007/s41468-023-00126-9</a>.","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Geometric characterization of the persistence of 1D maps,” <i>Journal of Applied and Computational Topology</i>. Springer Nature, 2023."}},{"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2791-4585"]},"doi":"10.15479/at:ista:14226","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","publisher":"Institute of Science and Technology Austria","department":[{"_id":"GradSch"},{"_id":"HeEd"}],"article_processing_charge":"No","author":[{"orcid":"0000-0002-6862-208X","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","full_name":"Stephenson, Elizabeth R","last_name":"Stephenson","first_name":"Elizabeth R"}],"day":"24","file":[{"checksum":"453caf851d75c3478c10ed09bd242a91","file_id":"14227","date_updated":"2024-02-26T23:30:03Z","access_level":"closed","date_created":"2023-08-24T13:02:49Z","file_name":"documents-export-2023-08-24.zip","creator":"cchlebak","embargo_to":"open_access","file_size":15501411,"content_type":"application/x-zip-compressed","relation":"source_file"},{"file_name":"thesis_pdf_a.pdf","creator":"cchlebak","file_size":6854783,"embargo":"2024-02-25","relation":"main_file","content_type":"application/pdf","checksum":"7349d29963d6695e555e171748648d9a","file_id":"14228","date_updated":"2024-02-26T23:30:03Z","access_level":"open_access","date_created":"2023-08-24T13:03:42Z"}],"title":"Generalizing medial axes with homology switches","degree_awarded":"MS","alternative_title":["ISTA Master's Thesis"],"status":"public","citation":{"chicago":"Stephenson, Elizabeth R. “Generalizing Medial Axes with Homology Switches.” Institute of Science and Technology Austria, 2023. <a href=\"https://doi.org/10.15479/at:ista:14226\">https://doi.org/10.15479/at:ista:14226</a>.","ieee":"E. R. Stephenson, “Generalizing medial axes with homology switches,” Institute of Science and Technology Austria, 2023.","short":"E.R. Stephenson, Generalizing Medial Axes with Homology Switches, Institute of Science and Technology Austria, 2023.","ama":"Stephenson ER. Generalizing medial axes with homology switches. 2023. doi:<a href=\"https://doi.org/10.15479/at:ista:14226\">10.15479/at:ista:14226</a>","apa":"Stephenson, E. R. (2023). <i>Generalizing medial axes with homology switches</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:14226\">https://doi.org/10.15479/at:ista:14226</a>","ista":"Stephenson ER. 2023. Generalizing medial axes with homology switches. Institute of Science and Technology Austria.","mla":"Stephenson, Elizabeth R. <i>Generalizing Medial Axes with Homology Switches</i>. Institute of Science and Technology Austria, 2023, doi:<a href=\"https://doi.org/10.15479/at:ista:14226\">10.15479/at:ista:14226</a>."},"publication_status":"published","oa":1,"has_accepted_license":"1","supervisor":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner"}],"ddc":["500"],"date_published":"2023-08-24T00:00:00Z","year":"2023","_id":"14226","page":"43","date_updated":"2024-02-26T23:30:04Z","abstract":[{"text":"We introduce the notion of a Faustian interchange in a 1-parameter family of smooth\r\nfunctions to generalize the medial axis to critical points of index larger than 0.\r\nWe construct and implement a general purpose algorithm for approximating such\r\ngeneralized medial axes.","lang":"eng"}],"type":"dissertation","oa_version":"Published Version","month":"08","date_created":"2023-08-24T13:01:18Z","file_date_updated":"2024-02-26T23:30:03Z"},{"publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"quality_controlled":"1","doi":"10.1007/s00453-022-01027-6","project":[{"call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","grant_number":"788183"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"language":[{"iso":"eng"}],"isi":1,"file":[{"relation":"main_file","content_type":"application/pdf","file_size":911017,"creator":"dernst","success":1,"file_name":"2023_Algorithmica_Edelsbrunner.pdf","date_created":"2023-01-20T10:02:48Z","access_level":"open_access","date_updated":"2023-01-20T10:02:48Z","file_id":"12322","checksum":"71685ca5121f4c837f40c3f8eb50c915"}],"day":"01","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"last_name":"Osang","first_name":"Georg F","full_name":"Osang, Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}],"title":"A simple algorithm for higher-order Delaunay mosaics and alpha shapes","department":[{"_id":"HeEd"}],"user_id":"2EBD1598-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","scopus_import":"1","article_processing_charge":"Yes (via OA deal)","ec_funded":1,"publication":"Algorithmica","has_accepted_license":"1","publication_status":"published","oa":1,"ddc":["510"],"date_published":"2023-01-01T00:00:00Z","external_id":{"isi":["000846967100001"]},"status":"public","citation":{"apa":"Edelsbrunner, H., &#38; Osang, G. F. (2023). A simple algorithm for higher-order Delaunay mosaics and alpha shapes. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-022-01027-6\">https://doi.org/10.1007/s00453-022-01027-6</a>","ista":"Edelsbrunner H, Osang GF. 2023. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. Algorithmica. 85, 277–295.","mla":"Edelsbrunner, Herbert, and Georg F. Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” <i>Algorithmica</i>, vol. 85, Springer Nature, 2023, pp. 277–95, doi:<a href=\"https://doi.org/10.1007/s00453-022-01027-6\">10.1007/s00453-022-01027-6</a>.","ama":"Edelsbrunner H, Osang GF. A simple algorithm for higher-order Delaunay mosaics and alpha shapes. <i>Algorithmica</i>. 2023;85:277-295. doi:<a href=\"https://doi.org/10.1007/s00453-022-01027-6\">10.1007/s00453-022-01027-6</a>","short":"H. Edelsbrunner, G.F. Osang, Algorithmica 85 (2023) 277–295.","chicago":"Edelsbrunner, Herbert, and Georg F Osang. “A Simple Algorithm for Higher-Order Delaunay Mosaics and Alpha Shapes.” <i>Algorithmica</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00453-022-01027-6\">https://doi.org/10.1007/s00453-022-01027-6</a>.","ieee":"H. Edelsbrunner and G. F. Osang, “A simple algorithm for higher-order Delaunay mosaics and alpha shapes,” <i>Algorithmica</i>, vol. 85. Springer Nature, pp. 277–295, 2023."},"intvolume":"        85","oa_version":"Published Version","type":"journal_article","month":"01","abstract":[{"text":"We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.","lang":"eng"}],"date_updated":"2023-06-27T12:53:43Z","page":"277-295","date_created":"2022-09-11T22:01:57Z","file_date_updated":"2023-01-20T10:02:48Z","volume":85,"year":"2023","acknowledgement":"Open access funding provided by Austrian Science Fund (FWF). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.","_id":"12086"},{"author":[{"last_name":"Boissonnat","first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel"},{"full_name":"Dyer, Ramsay","last_name":"Dyer","first_name":"Ramsay"},{"last_name":"Ghosh","first_name":"Arijit","full_name":"Ghosh, Arijit"},{"first_name":"Mathijs","last_name":"Wintraecken","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"day":"01","file":[{"creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":582850,"success":1,"file_name":"2023_DiscreteCompGeometry_Boissonnat.pdf","access_level":"open_access","date_created":"2023-02-02T11:01:10Z","checksum":"46352e0ee71e460848f88685ca852681","date_updated":"2023-02-02T11:01:10Z","file_id":"12488"}],"title":"Local criteria for triangulating general manifolds","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication":"Discrete & Computational Geometry","ec_funded":1,"scopus_import":"1","article_processing_charge":"No","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"doi":"10.1007/s00454-022-00431-7","quality_controlled":"1","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses","grant_number":"M03073"}],"isi":1,"keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"language":[{"iso":"eng"}],"page":"156-191","date_updated":"2023-08-01T12:47:32Z","abstract":[{"text":"We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.","lang":"eng"}],"month":"01","type":"journal_article","oa_version":"Published Version","volume":69,"date_created":"2023-01-16T10:04:06Z","file_date_updated":"2023-02-02T11:01:10Z","acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian Science Fund (FWF): M-3073. A part of the results described in this paper were presented at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science Fund (FWF).","year":"2023","_id":"12287","publication_status":"published","oa":1,"has_accepted_license":"1","date_published":"2023-01-01T00:00:00Z","ddc":["510"],"status":"public","external_id":{"isi":["000862193600001"]},"intvolume":"        69","citation":{"short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete &#38; Computational Geometry 69 (2023) 156–191.","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>.","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for triangulating general manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 69. Springer Nature, pp. 156–191, 2023.","apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., &#38; Wintraecken, M. (2023). Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>","ista":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating general manifolds. Discrete &#38; Computational Geometry. 69, 156–191.","mla":"Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 156–91, doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>.","ama":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. 2023;69:156-191. doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>"}},{"isi":1,"language":[{"iso":"eng"}],"issue":"3","project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"name":"The Wittgenstein Prize","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342"},{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Persistence and stability of geometric complexes"}],"doi":"10.1021/acs.jcim.2c01346","quality_controlled":"1","publication_identifier":{"eissn":["1549-960X"],"issn":["1549-9596"]},"publication":"Journal of Chemical Information and Modeling","article_processing_charge":"No","ec_funded":1,"scopus_import":"1","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publisher":"American Chemical Society","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","pmid":1,"department":[{"_id":"HeEd"}],"title":"Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives","author":[{"full_name":"Koehl, Patrice","first_name":"Patrice","last_name":"Koehl"},{"first_name":"Arseniy","last_name":"Akopyan","full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2548-617X"},{"first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"day":"13","file":[{"file_name":"2023_JCIM_Koehl.pdf","success":1,"file_size":8069223,"relation":"main_file","content_type":"application/pdf","creator":"dernst","file_id":"14070","date_updated":"2023-08-16T12:21:13Z","checksum":"7d20562269edff1e31b9d6019d4983b0","date_created":"2023-08-16T12:21:13Z","access_level":"open_access"}],"intvolume":"        63","citation":{"ama":"Koehl P, Akopyan A, Edelsbrunner H. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. <i>Journal of Chemical Information and Modeling</i>. 2023;63(3):973-985. doi:<a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">10.1021/acs.jcim.2c01346</a>","apa":"Koehl, P., Akopyan, A., &#38; Edelsbrunner, H. (2023). Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. <i>Journal of Chemical Information and Modeling</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">https://doi.org/10.1021/acs.jcim.2c01346</a>","mla":"Koehl, Patrice, et al. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” <i>Journal of Chemical Information and Modeling</i>, vol. 63, no. 3, American Chemical Society, 2023, pp. 973–85, doi:<a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">10.1021/acs.jcim.2c01346</a>.","ista":"Koehl P, Akopyan A, Edelsbrunner H. 2023. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. 63(3), 973–985.","chicago":"Koehl, Patrice, Arseniy Akopyan, and Herbert Edelsbrunner. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” <i>Journal of Chemical Information and Modeling</i>. American Chemical Society, 2023. <a href=\"https://doi.org/10.1021/acs.jcim.2c01346\">https://doi.org/10.1021/acs.jcim.2c01346</a>.","ieee":"P. Koehl, A. Akopyan, and H. Edelsbrunner, “Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives,” <i>Journal of Chemical Information and Modeling</i>, vol. 63, no. 3. American Chemical Society, pp. 973–985, 2023.","short":"P. Koehl, A. Akopyan, H. Edelsbrunner, Journal of Chemical Information and Modeling 63 (2023) 973–985."},"status":"public","external_id":{"isi":["000920370700001"],"pmid":["36638318"]},"date_published":"2023-02-13T00:00:00Z","ddc":["510","540"],"oa":1,"publication_status":"published","has_accepted_license":"1","_id":"12544","acknowledgement":"P.K. acknowledges support from the University of California Multicampus Research Programs and Initiatives (Grant No. M21PR3267) and from the NSF (Grant No.1760485). H.E. acknowledges support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.\r\nOpen Access is funded by the Austrian Science Fund (FWF).","year":"2023","volume":63,"file_date_updated":"2023-08-16T12:21:13Z","date_created":"2023-02-12T23:00:59Z","page":"973-985","abstract":[{"lang":"eng","text":"Geometry is crucial in our efforts to comprehend the structures and dynamics of biomolecules. For example, volume, surface area, and integrated mean and Gaussian curvature of the union of balls representing a molecule are used to quantify its interactions with the water surrounding it in the morphometric implicit solvent models. The Alpha Shape theory provides an accurate and reliable method for computing these geometric measures. In this paper, we derive homogeneous formulas for the expressions of these measures and their derivatives with respect to the atomic coordinates, and we provide algorithms that implement them into a new software package, AlphaMol. The only variables in these formulas are the interatomic distances, making them insensitive to translations and rotations. AlphaMol includes a sequential algorithm and a parallel algorithm. In the parallel version, we partition the atoms of the molecule of interest into 3D rectangular blocks, using a kd-tree algorithm. We then apply the sequential algorithm of AlphaMol to each block, augmented by a buffer zone to account for atoms whose ball representations may partially cover the block. The current parallel version of AlphaMol leads to a 20-fold speed-up compared to an independent serial implementation when using 32 processors. For instance, it takes 31 s to compute the geometric measures and derivatives of each atom in a viral capsid with more than 26 million atoms on 32 Intel processors running at 2.7 GHz. The presence of the buffer zones, however, leads to redundant computations, which ultimately limit the impact of using multiple processors. AlphaMol is available as an OpenSource software."}],"date_updated":"2023-08-16T12:22:07Z","type":"journal_article","month":"02","oa_version":"Published Version"},{"isi":1,"conference":{"start_date":"2022-11-28","name":"ICDMW: Conference on Data Mining Workshops","location":"Orlando, FL, United States","end_date":"2022-12-01"},"language":[{"iso":"eng"}],"doi":"10.1109/icdmw58026.2022.00093","quality_controlled":"1","publication_identifier":{"eisbn":["9798350346091"],"eissn":["2375-9259"]},"publication":"2022 IEEE International Conference on Data Mining Workshops","article_processing_charge":"No","publisher":"Institute of Electrical and Electronics Engineers","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"HeEd"}],"title":"Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic","article_number":"00093","author":[{"last_name":"Forghani","first_name":"Mohammad","full_name":"Forghani, Mohammad"},{"full_name":"Claramunt, Christophe","first_name":"Christophe","last_name":"Claramunt"},{"first_name":"Farid","last_name":"Karimipour","full_name":"Karimipour, Farid","orcid":"0000-0001-6746-4174","id":"2A2BCDC4-CF62-11E9-BE5E-3B1EE6697425"},{"last_name":"Heiler","first_name":"Georg","full_name":"Heiler, Georg"}],"day":"08","file":[{"checksum":"c253bee25e6dfe484f96662daa119cb6","file_id":"12549","date_updated":"2023-02-14T07:58:26Z","access_level":"open_access","date_created":"2023-02-14T07:58:26Z","file_name":"Visual Analysis_Mobility_COVID19 - SocDM2022.pdf","success":1,"creator":"fkarimip","file_size":1183339,"content_type":"application/pdf","relation":"main_file"}],"citation":{"short":"M. Forghani, C. Claramunt, F. Karimipour, G. Heiler, in:, 2022 IEEE International Conference on Data Mining Workshops, Institute of Electrical and Electronics Engineers, 2023.","ieee":"M. Forghani, C. Claramunt, F. Karimipour, and G. Heiler, “Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic,” in <i>2022 IEEE International Conference on Data Mining Workshops</i>, Orlando, FL, United States, 2023.","chicago":"Forghani, Mohammad, Christophe Claramunt, Farid Karimipour, and Georg Heiler. “Visual Analytics of Mobility Network Changes Observed Using Mobile Phone Data during COVID-19 Pandemic.” In <i>2022 IEEE International Conference on Data Mining Workshops</i>. Institute of Electrical and Electronics Engineers, 2023. <a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">https://doi.org/10.1109/icdmw58026.2022.00093</a>.","ista":"Forghani M, Claramunt C, Karimipour F, Heiler G. 2023. Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic. 2022 IEEE International Conference on Data Mining Workshops. ICDMW: Conference on Data Mining Workshops, 00093.","mla":"Forghani, Mohammad, et al. “Visual Analytics of Mobility Network Changes Observed Using Mobile Phone Data during COVID-19 Pandemic.” <i>2022 IEEE International Conference on Data Mining Workshops</i>, 00093, Institute of Electrical and Electronics Engineers, 2023, doi:<a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">10.1109/icdmw58026.2022.00093</a>.","apa":"Forghani, M., Claramunt, C., Karimipour, F., &#38; Heiler, G. (2023). Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic. In <i>2022 IEEE International Conference on Data Mining Workshops</i>. Orlando, FL, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">https://doi.org/10.1109/icdmw58026.2022.00093</a>","ama":"Forghani M, Claramunt C, Karimipour F, Heiler G. Visual analytics of mobility network changes observed using mobile phone data during COVID-19 pandemic. In: <i>2022 IEEE International Conference on Data Mining Workshops</i>. Institute of Electrical and Electronics Engineers; 2023. doi:<a href=\"https://doi.org/10.1109/icdmw58026.2022.00093\">10.1109/icdmw58026.2022.00093</a>"},"external_id":{"isi":["000971492200145"]},"status":"public","ddc":["600"],"date_published":"2023-02-08T00:00:00Z","publication_status":"published","oa":1,"has_accepted_license":"1","_id":"12548","year":"2023","date_created":"2023-02-14T07:56:21Z","file_date_updated":"2023-02-14T07:58:26Z","date_updated":"2023-08-01T13:15:48Z","abstract":[{"text":"The limited exchange between human communities is a key factor in preventing the spread of COVID-19. This paper introduces a digital framework that combines an integration of real mobility data at the country scale with a series of modeling techniques and visual capabilities that highlight mobility patterns before and during the pandemic. The findings not only significantly exhibit mobility trends and different degrees of similarities at regional and local levels but also provide potential insight into the emergence of a pandemic on human behavior patterns and their likely socio-economic impacts.","lang":"eng"}],"type":"conference","oa_version":"Submitted Version","month":"02"},{"quality_controlled":"1","doi":"10.1007/s00454-022-00476-8","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"language":[{"iso":"eng"}],"isi":1,"arxiv":1,"title":"Computing the multicover bifiltration","file":[{"success":1,"file_name":"2023_DisCompGeo_Corbet.pdf","relation":"main_file","content_type":"application/pdf","file_size":1359323,"creator":"cchlebak","date_updated":"2023-03-07T14:40:14Z","file_id":"12715","checksum":"71ce7e59f7ee4620acc704fecca620c2","date_created":"2023-03-07T14:40:14Z","access_level":"open_access"}],"day":"01","author":[{"last_name":"Corbet","first_name":"René","full_name":"Corbet, René"},{"last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299"},{"full_name":"Lesnick, Michael","last_name":"Lesnick","first_name":"Michael"},{"last_name":"Osang","first_name":"Georg F","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","article_processing_charge":"Yes (via OA deal)","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"publication":"Discrete and Computational Geometry","department":[{"_id":"HeEd"}],"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"date_published":"2023-09-01T00:00:00Z","has_accepted_license":"1","publication_status":"published","oa":1,"citation":{"mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” <i>Discrete and Computational Geometry</i>, vol. 70, Springer Nature, 2023, pp. 376–405, doi:<a href=\"https://doi.org/10.1007/s00454-022-00476-8\">10.1007/s00454-022-00476-8</a>.","ista":"Corbet R, Kerber M, Lesnick M, Osang GF. 2023. Computing the multicover bifiltration. Discrete and Computational Geometry. 70, 376–405.","apa":"Corbet, R., Kerber, M., Lesnick, M., &#38; Osang, G. F. (2023). Computing the multicover bifiltration. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00476-8\">https://doi.org/10.1007/s00454-022-00476-8</a>","ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. <i>Discrete and Computational Geometry</i>. 2023;70:376-405. doi:<a href=\"https://doi.org/10.1007/s00454-022-00476-8\">10.1007/s00454-022-00476-8</a>","short":"R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, Discrete and Computational Geometry 70 (2023) 376–405.","ieee":"R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover bifiltration,” <i>Discrete and Computational Geometry</i>, vol. 70. Springer Nature, pp. 376–405, 2023.","chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00476-8\">https://doi.org/10.1007/s00454-022-00476-8</a>."},"intvolume":"        70","related_material":{"record":[{"relation":"earlier_version","id":"9605","status":"public"}]},"status":"public","external_id":{"arxiv":["2103.07823"],"isi":["000936496800001"]},"file_date_updated":"2023-03-07T14:40:14Z","date_created":"2023-03-05T23:01:06Z","volume":70,"abstract":[{"lang":"eng","text":"Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness."}],"date_updated":"2023-10-04T12:03:40Z","month":"09","oa_version":"Published Version","type":"journal_article","page":"376-405","_id":"12709","year":"2023","acknowledgement":"We thank the anonymous reviewers for many helpful comments and suggestions, which led to substantial improvements of the paper. The first two authors were supported by the Austrian Science Fund (FWF) grant number P 29984-N35 and W1230. The first author was partly supported by an Austrian Marshall Plan Scholarship, and by the Brummer & Partners MathDataLab. A conference version of this paper was presented at the 37th International Symposium on Computational Geometry (SoCG 2021). Open access funding provided by the Royal Institute of Technology."},{"page":"619-641","oa_version":"Submitted Version","month":"09","type":"journal_article","date_updated":"2023-10-04T12:07:18Z","abstract":[{"text":"Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift 176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert showed that sets of positive reach in Euclidean space and Riemannian manifolds are very similar. In this paper we introduce a slight variant of Kleinjohann’s and Bangert’s extension and quantify the similarity between sets of positive reach in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we bound the local feature size (a local version of the reach) of its lifting to the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated by the importance of the reach and local feature size to manifold learning, topological inference, and triangulating manifolds and the fact that intrinsic approaches circumvent the curse of dimensionality.","lang":"eng"}],"volume":7,"date_created":"2023-03-26T22:01:08Z","acknowledgement":"We thank Eddie Aamari, David Cohen-Steiner, Isa Costantini, Fred Chazal, Ramsay Dyer, André Lieutier, and Alef Sterk for discussion and Pierre Pansu for encouragement. We further acknowledge the anonymous reviewers whose comments helped improve the exposition.\r\nThe research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions). The first author is further supported by the French government, through the 3IA Côte d’Azur Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002. The second author is supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411 and the Austrian science fund (FWF) M-3073.","year":"2023","_id":"12763","oa":1,"publication_status":"published","date_published":"2023-09-01T00:00:00Z","main_file_link":[{"url":"https://inserm.hal.science/INRIA-SACLAY/hal-04083524v1","open_access":"1"}],"status":"public","intvolume":"         7","citation":{"short":"J.D. Boissonnat, M. Wintraecken, Journal of Applied and Computational Topology 7 (2023) 619–641.","ieee":"J. D. Boissonnat and M. Wintraecken, “The reach of subsets of manifolds,” <i>Journal of Applied and Computational Topology</i>, vol. 7. Springer Nature, pp. 619–641, 2023.","chicago":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” <i>Journal of Applied and Computational Topology</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s41468-023-00116-x\">https://doi.org/10.1007/s41468-023-00116-x</a>.","ista":"Boissonnat JD, Wintraecken M. 2023. The reach of subsets of manifolds. Journal of Applied and Computational Topology. 7, 619–641.","mla":"Boissonnat, Jean Daniel, and Mathijs Wintraecken. “The Reach of Subsets of Manifolds.” <i>Journal of Applied and Computational Topology</i>, vol. 7, Springer Nature, 2023, pp. 619–41, doi:<a href=\"https://doi.org/10.1007/s41468-023-00116-x\">10.1007/s41468-023-00116-x</a>.","apa":"Boissonnat, J. D., &#38; Wintraecken, M. (2023). The reach of subsets of manifolds. <i>Journal of Applied and Computational Topology</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s41468-023-00116-x\">https://doi.org/10.1007/s41468-023-00116-x</a>","ama":"Boissonnat JD, Wintraecken M. The reach of subsets of manifolds. <i>Journal of Applied and Computational Topology</i>. 2023;7:619-641. doi:<a href=\"https://doi.org/10.1007/s41468-023-00116-x\">10.1007/s41468-023-00116-x</a>"},"author":[{"first_name":"Jean Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean Daniel"},{"full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs","last_name":"Wintraecken"}],"day":"01","title":"The reach of subsets of manifolds","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication":"Journal of Applied and Computational Topology","article_type":"original","ec_funded":1,"scopus_import":"1","article_processing_charge":"No","publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"doi":"10.1007/s41468-023-00116-x","quality_controlled":"1","project":[{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"},{"grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses"}],"language":[{"iso":"eng"}]},{"isi":1,"language":[{"iso":"eng"}],"project":[{"grant_number":"I04245","_id":"26AD5D90-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algebraic Footprints of Geometric Features in Homology"}],"doi":"10.1007/s00454-023-00484-2","quality_controlled":"1","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publication":"Discrete and Computational Geometry","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"scopus_import":"1","article_processing_charge":"Yes (via OA deal)","publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"title":"Discrete yamabe problem for polyhedral surfaces","author":[{"last_name":"Kourimska","first_name":"Hana","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","orcid":"0000-0001-7841-0091","full_name":"Kourimska, Hana"}],"day":"01","file":[{"access_level":"open_access","date_created":"2023-10-04T11:46:24Z","checksum":"cdbf90ba4a7ddcb190d37b9e9d4cb9d3","date_updated":"2023-10-04T11:46:24Z","file_id":"14396","creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":1026683,"success":1,"file_name":"2023_DiscreteGeometry_Kourimska.pdf"}],"intvolume":"        70","citation":{"short":"H. Kourimska, Discrete and Computational Geometry 70 (2023) 123–153.","chicago":"Kourimska, Hana. “Discrete Yamabe Problem for Polyhedral Surfaces.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-023-00484-2\">https://doi.org/10.1007/s00454-023-00484-2</a>.","ieee":"H. Kourimska, “Discrete yamabe problem for polyhedral surfaces,” <i>Discrete and Computational Geometry</i>, vol. 70. Springer Nature, pp. 123–153, 2023.","apa":"Kourimska, H. (2023). Discrete yamabe problem for polyhedral surfaces. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00484-2\">https://doi.org/10.1007/s00454-023-00484-2</a>","ista":"Kourimska H. 2023. Discrete yamabe problem for polyhedral surfaces. Discrete and Computational Geometry. 70, 123–153.","mla":"Kourimska, Hana. “Discrete Yamabe Problem for Polyhedral Surfaces.” <i>Discrete and Computational Geometry</i>, vol. 70, Springer Nature, 2023, pp. 123–53, doi:<a href=\"https://doi.org/10.1007/s00454-023-00484-2\">10.1007/s00454-023-00484-2</a>.","ama":"Kourimska H. Discrete yamabe problem for polyhedral surfaces. <i>Discrete and Computational Geometry</i>. 2023;70:123-153. doi:<a href=\"https://doi.org/10.1007/s00454-023-00484-2\">10.1007/s00454-023-00484-2</a>"},"status":"public","external_id":{"isi":["000948148000001"]},"ddc":["510"],"date_published":"2023-07-01T00:00:00Z","publication_status":"published","oa":1,"has_accepted_license":"1","_id":"12764","acknowledgement":"Open access funding provided by the Austrian Science Fund (FWF). This research was supported by the FWF grant, Project number I4245-N35, and by the Deutsche Forschungsgemeinschaft (DFG - German Research Foundation) - Project-ID 195170736 - TRR109.","year":"2023","volume":70,"file_date_updated":"2023-10-04T11:46:24Z","date_created":"2023-03-26T22:01:09Z","page":"123-153","oa_version":"Published Version","type":"journal_article","month":"07","date_updated":"2023-10-04T11:46:48Z","abstract":[{"lang":"eng","text":"We study a new discretization of the Gaussian curvature for polyhedral surfaces. This discrete Gaussian curvature is defined on each conical singularity of a polyhedral surface as the quotient of the angle defect and the area of the Voronoi cell corresponding to the singularity. We divide polyhedral surfaces into discrete conformal classes using a generalization of discrete conformal equivalence pioneered by Feng Luo. We subsequently show that, in every discrete conformal class, there exists a polyhedral surface with constant discrete Gaussian curvature. We also provide explicit examples to demonstrate that this surface is in general not unique."}]},{"acknowledgement":"This work was begun at the University of Waterloo and was partially supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n","year":"2023","_id":"12833","oa_version":"Published Version","month":"01","type":"journal_article","abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"date_updated":"2024-01-04T12:42:09Z","volume":24,"file_date_updated":"2023-04-17T08:10:28Z","date_created":"2023-04-16T22:01:08Z","status":"public","external_id":{"arxiv":["1903.06981"]},"related_material":{"record":[{"relation":"earlier_version","id":"7950","status":"public"}]},"intvolume":"        24","citation":{"ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. 2023;24(2). doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (2023). Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 24(2), 9.","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences, 2023. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>.","ieee":"A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2. EPI Sciences, 2023.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science 24 (2023)."},"publication_status":"published","oa":1,"has_accepted_license":"1","date_published":"2023-01-18T00:00:00Z","ddc":["000"],"publisher":"EPI Sciences","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"},{"_id":"HeEd"},{"_id":"UlWa"}],"publication":"Discrete Mathematics and Theoretical Computer Science","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","scopus_import":"1","article_processing_charge":"No","author":[{"last_name":"Biniaz","first_name":"Ahmad","full_name":"Biniaz, Ahmad"},{"last_name":"Jain","first_name":"Kshitij","full_name":"Jain, Kshitij"},{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"full_name":"Miltzow, Tillmann","last_name":"Miltzow","first_name":"Tillmann"},{"full_name":"Mondal, Debajyoti","first_name":"Debajyoti","last_name":"Mondal"},{"full_name":"Naredla, Anurag Murty","first_name":"Anurag Murty","last_name":"Naredla"},{"orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","full_name":"Tkadlec, Josef","last_name":"Tkadlec","first_name":"Josef"},{"first_name":"Alexi","last_name":"Turcotte","full_name":"Turcotte, Alexi"}],"day":"18","file":[{"checksum":"439102ea4f6e2aeefd7107dfb9ccf532","file_id":"12844","date_updated":"2023-04-17T08:10:28Z","access_level":"open_access","date_created":"2023-04-17T08:10:28Z","file_name":"2022_DMTCS_Biniaz.pdf","success":1,"creator":"dernst","file_size":2072197,"content_type":"application/pdf","relation":"main_file"}],"article_number":"9","title":"Token swapping on trees","arxiv":1,"issue":"2","language":[{"iso":"eng"}],"publication_identifier":{"issn":["1462-7264"],"eissn":["1365-8050"]},"doi":"10.46298/DMTCS.8383","quality_controlled":"1"},{"acknowledgement":"The authors have received funding from the European Research Council under the European Union's ERC grant greement 339025 GUDHI (Algorithmic Foundations of Geometric Un-derstanding  in  Higher  Dimensions).   The  first  author  was  supported  by  the  French  government,through the 3IA C\\^ote d'Azur Investments in the Future project managed by the National ResearchAgency (ANR) with the reference ANR-19-P3IA-0002.  The third author was supported by the Eu-ropean Union's Horizon 2020 research and innovation programme under the Marie Sk\\lodowska-Curiegrant agreement 754411 and the FWF (Austrian Science Fund) grant M 3073.","year":"2023","_id":"12960","page":"452-486","date_updated":"2023-10-10T07:34:35Z","abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider its piecewise linear (PL) approximation M^\r\n based on a triangulation T of the ambient space Rd. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ=1/D (and unavoidably exponential in n). Since it is known that for δ=Ω(d2.5), M^ is O(D2)-close and isotopic to M\r\n, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M^ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. ","lang":"eng"}],"type":"journal_article","month":"04","oa_version":"Submitted Version","volume":52,"date_created":"2023-05-14T22:01:00Z","external_id":{"isi":["001013183000012"]},"status":"public","related_material":{"record":[{"status":"public","id":"9441","relation":"earlier_version"}]},"intvolume":"        52","citation":{"apa":"Boissonnat, J. D., Kachanovich, S., &#38; Wintraecken, M. (2023). Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/21M1412918\">https://doi.org/10.1137/21M1412918</a>","mla":"Boissonnat, Jean Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” <i>SIAM Journal on Computing</i>, vol. 52, no. 2, Society for Industrial and Applied Mathematics, 2023, pp. 452–86, doi:<a href=\"https://doi.org/10.1137/21M1412918\">10.1137/21M1412918</a>.","ista":"Boissonnat JD, Kachanovich S, Wintraecken M. 2023. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. 52(2), 452–486.","ama":"Boissonnat JD, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. <i>SIAM Journal on Computing</i>. 2023;52(2):452-486. doi:<a href=\"https://doi.org/10.1137/21M1412918\">10.1137/21M1412918</a>","short":"J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing 52 (2023) 452–486.","chicago":"Boissonnat, Jean Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/21M1412918\">https://doi.org/10.1137/21M1412918</a>.","ieee":"J. D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations,” <i>SIAM Journal on Computing</i>, vol. 52, no. 2. Society for Industrial and Applied Mathematics, pp. 452–486, 2023."},"publication_status":"published","oa":1,"date_published":"2023-04-30T00:00:00Z","main_file_link":[{"url":"https://hal-emse.ccsd.cnrs.fr/3IA-COTEDAZUR/hal-04083489v1","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"HeEd"}],"publication":"SIAM Journal on Computing","scopus_import":"1","ec_funded":1,"article_processing_charge":"No","article_type":"original","author":[{"full_name":"Boissonnat, Jean Daniel","last_name":"Boissonnat","first_name":"Jean Daniel"},{"full_name":"Kachanovich, Siargey","last_name":"Kachanovich","first_name":"Siargey"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","last_name":"Wintraecken","first_name":"Mathijs"}],"day":"30","title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"},{"name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073"}],"isi":1,"language":[{"iso":"eng"}],"issue":"2","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"doi":"10.1137/21M1412918","quality_controlled":"1"}]