[{"related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"20260"},{"id":"21050","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"21051","status":"public"}]},"_id":"21021","date_published":"2026-01-21T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published","department":[{"_id":"GradSch"},{"_id":"HeEd"},{"_id":"UlWa"}],"degree_awarded":"PhD","title":"Braiding geometry and topology to study shapes and data","article_processing_charge":"No","date_created":"2026-01-20T21:38:40Z","oa_version":"Published Version","doi":"10.15479/AT-ISTA-21021","abstract":[{"text":"This thesis examines how geometry and topology intersect in the representation, transformation, and analysis of complex shapes. It considers how continuous manifolds relate to their discrete analogues, how topological structures evolve in persistence vineyards, and how tools from topological data analysis can illuminate problems in mathematical physics. Central to this exploration is the question of how structure, both geometric and topological, persists or changes under approximation, sampling, or deformation. The work develops new approaches to skeletal and grid-based representations of surfaces, reveals the full expressive capacity of persistence vineyards, and applies topological methods to the longstanding problem of equilibria in electrostatic fields. These threads braid together into a broader understanding of how topology and geometry inform one another across theory, computation, and application.","lang":"eng"}],"type":"dissertation","file_date_updated":"2026-01-30T11:40:09Z","month":"01","publication_identifier":{"issn":["2663-337X"]},"corr_author":"1","acknowledgement":"The research presented in this thesis was funded by the DFG Collaborative Research\r\nCenter TRR 109, ‘Discretization in Geometry and Dynamics’.\r\n","year":"2026","author":[{"last_name":"Fillmore","first_name":"Christopher D","full_name":"Fillmore, Christopher D","id":"35638A5C-AAC7-11E9-B0BF-5503E6697425"}],"date_updated":"2026-04-07T11:42:49Z","acknowledged_ssus":[{"_id":"M-Shop"},{"_id":"ScienComp"}],"has_accepted_license":"1","publisher":"Institute of Science and Technology Austria","file":[{"file_size":55954297,"content_type":"application/pdf","checksum":"4c0889130095c31d4e5088c5b8dfd607","date_updated":"2026-01-30T11:40:09Z","access_level":"open_access","date_created":"2026-01-26T19:44:46Z","file_name":"2025_Fillmore_Christopher_Thesis.pdf","creator":"cfillmor","file_id":"21046","relation":"main_file"},{"creator":"cfillmor","file_name":"Thesis.zip","relation":"source_file","file_id":"21047","checksum":"d69afb71d82ab98f856886126ee7303a","content_type":"application/x-zip-compressed","file_size":166080788,"date_updated":"2026-01-26T19:46:20Z","access_level":"closed","date_created":"2026-01-26T19:46:20Z"}],"status":"public","page":"122","citation":{"ista":"Fillmore CD. 2026. Braiding geometry and topology to study shapes and data. Institute of Science and Technology Austria.","short":"C.D. Fillmore, Braiding Geometry and Topology to Study Shapes and Data, Institute of Science and Technology Austria, 2026.","chicago":"Fillmore, Christopher D. “Braiding Geometry and Topology to Study Shapes and Data.” Institute of Science and Technology Austria, 2026. <a href=\"https://doi.org/10.15479/AT-ISTA-21021\">https://doi.org/10.15479/AT-ISTA-21021</a>.","ama":"Fillmore CD. Braiding geometry and topology to study shapes and data. 2026. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21021\">10.15479/AT-ISTA-21021</a>","ieee":"C. D. Fillmore, “Braiding geometry and topology to study shapes and data,” Institute of Science and Technology Austria, 2026.","apa":"Fillmore, C. D. (2026). <i>Braiding geometry and topology to study shapes and data</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-21021\">https://doi.org/10.15479/AT-ISTA-21021</a>","mla":"Fillmore, Christopher D. <i>Braiding Geometry and Topology to Study Shapes and Data</i>. Institute of Science and Technology Austria, 2026, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21021\">10.15479/AT-ISTA-21021</a>."},"ddc":["514","516"],"alternative_title":["ISTA Thesis"],"day":"21","OA_place":"publisher","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","supervisor":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner"},{"last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"}},{"article_type":"original","quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)"},"day":"17","OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":51,"issue":"1","file":[{"checksum":"442023926a3803d5d6ca8db8dbc4af1c","content_type":"application/pdf","file_size":342082,"success":1,"date_created":"2026-04-28T12:03:13Z","access_level":"open_access","date_updated":"2026-04-28T12:03:13Z","file_id":"21772","relation":"main_file","file_name":"2026_AnnalesFenniciMath_Dymond.pdf","creator":"dernst"}],"publisher":"Finnish Mathematical Society","scopus_import":"1","has_accepted_license":"1","publication":"Annales Fennici Mathematici","status":"public","OA_type":"hybrid","citation":{"ista":"Dymond M, Kaluza V. 2026. Extending bilipschitz mappings between separated nets. Annales Fennici Mathematici. 51(1), 237–260.","chicago":"Dymond, Michael, and Vojtech Kaluza. “Extending Bilipschitz Mappings between Separated Nets.” <i>Annales Fennici Mathematici</i>. Finnish Mathematical Society, 2026. <a href=\"https://doi.org/10.54330/afm.181562\">https://doi.org/10.54330/afm.181562</a>.","short":"M. Dymond, V. Kaluza, Annales Fennici Mathematici 51 (2026) 237–260.","ieee":"M. Dymond and V. Kaluza, “Extending bilipschitz mappings between separated nets,” <i>Annales Fennici Mathematici</i>, vol. 51, no. 1. Finnish Mathematical Society, pp. 237–260, 2026.","ama":"Dymond M, Kaluza V. Extending bilipschitz mappings between separated nets. <i>Annales Fennici Mathematici</i>. 2026;51(1):237-260. doi:<a href=\"https://doi.org/10.54330/afm.181562\">10.54330/afm.181562</a>","mla":"Dymond, Michael, and Vojtech Kaluza. “Extending Bilipschitz Mappings between Separated Nets.” <i>Annales Fennici Mathematici</i>, vol. 51, no. 1, Finnish Mathematical Society, 2026, pp. 237–60, doi:<a href=\"https://doi.org/10.54330/afm.181562\">10.54330/afm.181562</a>.","apa":"Dymond, M., &#38; Kaluza, V. (2026). Extending bilipschitz mappings between separated nets. <i>Annales Fennici Mathematici</i>. Finnish Mathematical Society. <a href=\"https://doi.org/10.54330/afm.181562\">https://doi.org/10.54330/afm.181562</a>"},"page":"237-260","ddc":["510"],"author":[{"first_name":"Michael","last_name":"Dymond","full_name":"Dymond, Michael"},{"last_name":"Kaluza","first_name":"Vojtech","full_name":"Kaluza, Vojtech","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","orcid":"0000-0002-2512-8698"}],"year":"2026","date_updated":"2026-04-28T12:06:00Z","arxiv":1,"month":"04","type":"journal_article","file_date_updated":"2026-04-28T12:03:13Z","abstract":[{"lang":"eng","text":"We provide a new characterisation of the decades old open problem of extending bilipschitz mappings given on a Euclidean separated net. In particular, this allows for the complete positive solution of the open problem in dimension two. Along the way, we develop a set of tools for bilipschitz extensions of mappings between subsets of Euclidean spaces."}],"external_id":{"arxiv":["2507.22007"]},"project":[{"_id":"fc35eaa2-9c52-11eb-aca3-88501ab155e9","grant_number":"M03100","name":"Spectra and topology of graphs and of simplicial complexes"}],"publication_identifier":{"eissn":["2737-114X"],"issn":["2737-0690"]},"acknowledgement":"The present work developed from a research visit of M.D. to V.K. at IST Austria, funded by\r\na London Mathematical Society Research in Pairs grant. This work was done while V.K. was fully funded by the Austria Science Fund (FWF) [M 3100-N].","corr_author":"1","department":[{"_id":"UlWa"}],"title":"Extending bilipschitz mappings between separated nets","oa_version":"Published Version","license":"https://creativecommons.org/licenses/by-nc/4.0/","doi":"10.54330/afm.181562","date_created":"2026-04-26T22:01:47Z","article_processing_charge":"Yes (in subscription journal)","language":[{"iso":"eng"}],"intvolume":"        51","publication_status":"published","_id":"21766","keyword":["Lipschitz","bilipschitz","extension","separated net."],"date_published":"2026-04-17T00:00:00Z"},{"publication_status":"published","intvolume":"        47","language":[{"iso":"eng"}],"date_published":"2025-03-01T00:00:00Z","_id":"18157","isi":1,"publication_identifier":{"issn":["0343-6993"]},"acknowledgement":"Open access funding provided by Copenhagen University.","abstract":[{"text":"Interest in sliding block puzzles dates back to the 15-puzzle, seemingly invented by Noyes Chapman in 1874 (see [23] for an account of the fascinating history of the puzzle). The game consists of fifteen movable square blocks numbered \r\n and arranged within a \r\n square box, leaving one empty space (see Figure 1). The task at hand is to start from a given configuration of the numbered blocks and reach the desired target configuration, where the only allowed move is to slide a numbered block into an adjacent empty space. This task seemed to be unpredictably either very easy to accomplish, or completely impossible, and the puzzle turned into a worldwide sensation in the spring of 1880. A particularly challenging instance, known as the 13-15-14 puzzle, consisted of initial and target configurations that differed by a single swap (historically this swap involved the blocks labeled 14 and 15). The craze of this puzzle was such that it consistently made newspaper headlines in 1880, with an article in the New York Times lamenting that it was “threatening our free institutions” [23, p. 9]. Various prizes were offered for anyone who could solve this challenge, beginning with a $25 set of teeth and culminating with Sam Loyd’s famous $1,000 cash prize.","lang":"eng"}],"type":"journal_article","file_date_updated":"2025-04-08T11:17:45Z","month":"03","arxiv":1,"external_id":{"arxiv":["2303.09459"],"isi":["001318056000001"]},"title":"Books, Hallways, and social butterflies: A note on sliding block puzzles","article_processing_charge":"Yes (via OA deal)","date_created":"2024-09-29T22:01:38Z","doi":"10.1007/s00283-024-10358-x","oa_version":"Published Version","department":[{"_id":"UlWa"},{"_id":"MaKw"}],"publication":"Mathematical Intelligencer","status":"public","OA_type":"hybrid","citation":{"apa":"Brunck, F. R., &#38; Kwan, M. A. (2025). Books, Hallways, and social butterflies: A note on sliding block puzzles. <i>Mathematical Intelligencer</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00283-024-10358-x\">https://doi.org/10.1007/s00283-024-10358-x</a>","ieee":"F. R. Brunck and M. A. Kwan, “Books, Hallways, and social butterflies: A note on sliding block puzzles,” <i>Mathematical Intelligencer</i>, vol. 47. Springer Nature, pp. 52–65, 2025.","ama":"Brunck FR, Kwan MA. Books, Hallways, and social butterflies: A note on sliding block puzzles. <i>Mathematical Intelligencer</i>. 2025;47:52-65. doi:<a href=\"https://doi.org/10.1007/s00283-024-10358-x\">10.1007/s00283-024-10358-x</a>","mla":"Brunck, Florestan R., and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” <i>Mathematical Intelligencer</i>, vol. 47, Springer Nature, 2025, pp. 52–65, doi:<a href=\"https://doi.org/10.1007/s00283-024-10358-x\">10.1007/s00283-024-10358-x</a>.","chicago":"Brunck, Florestan R, and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” <i>Mathematical Intelligencer</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s00283-024-10358-x\">https://doi.org/10.1007/s00283-024-10358-x</a>.","short":"F.R. Brunck, M.A. Kwan, Mathematical Intelligencer 47 (2025) 52–65.","ista":"Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. 47, 52–65."},"ddc":["510"],"page":"52-65","has_accepted_license":"1","scopus_import":"1","publisher":"Springer Nature","file":[{"relation":"main_file","file_id":"19530","creator":"dernst","file_name":"2025_MathIntelligencer_Brunck.pdf","content_type":"application/pdf","file_size":1760643,"checksum":"c932ebe45c460d4a73f5b2dcca643db1","success":1,"date_created":"2025-04-08T11:17:45Z","access_level":"open_access","date_updated":"2025-04-08T11:17:45Z"}],"date_updated":"2025-05-19T14:00:09Z","year":"2025","author":[{"id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","first_name":"Florestan R","last_name":"Brunck","full_name":"Brunck, Florestan R"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"quality_controlled":"1","article_type":"original","oa":1,"volume":47,"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher"},{"OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","issue":"1","volume":24,"oa":1,"quality_controlled":"1","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"year":"2025","author":[{"orcid":"0000-0001-9789-9750","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e","full_name":"Lipiński, Michał","last_name":"Lipiński","first_name":"Michał"},{"last_name":"Mischaikow","first_name":"Konstantin","full_name":"Mischaikow, Konstantin"},{"first_name":"Marian","last_name":"Mrozek","full_name":"Mrozek, Marian"}],"date_updated":"2025-04-14T07:54:56Z","has_accepted_license":"1","scopus_import":"1","ec_funded":1,"file":[{"creator":"mlipinsk","file_name":"2025_predecomposition.pdf","relation":"main_file","file_id":"18595","access_level":"open_access","date_updated":"2024-11-28T06:52:38Z","date_created":"2024-11-28T06:52:38Z","success":1,"content_type":"application/pdf","checksum":"73309a57cc798d696caa57b6aa1467d8","file_size":1483668}],"publisher":"Springer Nature","article_number":"5","OA_type":"hybrid","ddc":["514","510"],"citation":{"ieee":"M. Lipiński, K. Mischaikow, and M. Mrozek, “Morse predecomposition of an invariant set,” <i>Qualitative Theory of Dynamical Systems</i>, vol. 24, no. 1. Springer Nature, 2025.","mla":"Lipiński, Michał, et al. “Morse Predecomposition of an Invariant Set.” <i>Qualitative Theory of Dynamical Systems</i>, vol. 24, no. 1, 5, Springer Nature, 2025, doi:<a href=\"https://doi.org/10.1007/s12346-024-01144-3\">10.1007/s12346-024-01144-3</a>.","apa":"Lipiński, M., Mischaikow, K., &#38; Mrozek, M. (2025). Morse predecomposition of an invariant set. <i>Qualitative Theory of Dynamical Systems</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s12346-024-01144-3\">https://doi.org/10.1007/s12346-024-01144-3</a>","ama":"Lipiński M, Mischaikow K, Mrozek M. Morse predecomposition of an invariant set. <i>Qualitative Theory of Dynamical Systems</i>. 2025;24(1). doi:<a href=\"https://doi.org/10.1007/s12346-024-01144-3\">10.1007/s12346-024-01144-3</a>","ista":"Lipiński M, Mischaikow K, Mrozek M. 2025. Morse predecomposition of an invariant set. Qualitative Theory of Dynamical Systems. 24(1), 5.","short":"M. Lipiński, K. Mischaikow, M. Mrozek, Qualitative Theory of Dynamical Systems 24 (2025).","chicago":"Lipiński, Michał, Konstantin Mischaikow, and Marian Mrozek. “Morse Predecomposition of an Invariant Set.” <i>Qualitative Theory of Dynamical Systems</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s12346-024-01144-3\">https://doi.org/10.1007/s12346-024-01144-3</a>."},"status":"public","publication":"Qualitative Theory of Dynamical Systems","department":[{"_id":"UlWa"}],"article_processing_charge":"Yes (via OA deal)","date_created":"2024-11-24T23:01:47Z","oa_version":"Published Version","doi":"10.1007/s12346-024-01144-3","title":"Morse predecomposition of an invariant set","project":[{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"external_id":{"isi":["001356000500005"],"arxiv":["2312.08013"]},"abstract":[{"text":"Motivated by the study of recurrent orbits and dynamics within a Morse set of a Morse decomposition we introduce the concept of Morse predecomposition of an isolated invariant set within the setting of both combinatorial and classical dynamical systems. While Morse decomposition summarizes solely the gradient part of a dynamical system, the developed generalization extends to the recurrent component as well. In particular, a chain recurrent set, which is indecomposable in terms of Morse decomposition, can be represented more finely in the Morse predecomposition framework. This generalization is achieved by forgoing the poset structure inherent to Morse decomposition and relaxing the notion of connection between Morse sets (elements of Morse decomposition) in favor of what we term ’links’. We prove that a Morse decomposition is a special case of Morse predecomposition indexed by a poset. Additionally, we show how a Morse predecomposition may be condensed back to retrieve a Morse decomposition.","lang":"eng"}],"arxiv":1,"type":"journal_article","month":"02","file_date_updated":"2024-11-28T06:52:38Z","corr_author":"1","acknowledgement":"M.L. acknowledge support by the Dioscuri program initiated by the Max Planck Society, jointly managed with the National Science Centre (Poland), and mutually funded by the Polish Ministry of Science and Higher Education and the German Federal Ministry of Education and Research. M.L. also acknowledges that this project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413. Research of M.M. is partially supported by the Polish National Science Center under Opus Grant No. 2019/35/B/ST1/00874. The work of K.M. was partially supported by the National Science Foundation under awards DMS-1839294 and HDR TRIPODS award CCF-1934924, DARPA contract HR0011-16-2-0033, National Institutes of Health award R01 GM126555, Air Force Office of Scientific Research under award numbers FA9550-23-1-0011, AWD00010853-MOD002 and MURI FA9550-23-1-0400. K.M. was also supported by a grant from the Simons Foundation. Open access funding provided by Institute of Science and Technology (IST Austria). ","publication_identifier":{"eissn":["1662-3592"],"issn":["1575-5460"]},"_id":"18580","isi":1,"date_published":"2025-02-01T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"        24"},{"publication_status":"epub_ahead","language":[{"iso":"eng"}],"date_published":"2025-05-26T00:00:00Z","isi":1,"_id":"19848","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria).","corr_author":"1","publication_identifier":{"eissn":["1572-8382"],"issn":["0924-8463"]},"external_id":{"isi":["001494836700001"],"arxiv":["2407.07004"]},"type":"journal_article","arxiv":1,"month":"05","abstract":[{"text":"Binding precedents (súmulas vinculantes) constitute a juridical instrument unique to the Brazilian legal system and whose objectives include the protection of the Federal Supreme Court against repetitive demands. Studies of the effectiveness of these instruments in decreasing the Court’s exposure to similar cases, however, indicate that they tend to fail in such a direction, with some of the binding precedents seemingly creating new demands. We empirically assess the legal impact of five binding precedents, 11, 14, 17, 26, and 37, at the highest Court level through their effects on the legal subjects they address. This analysis is only possible through the comparison of the Court’s ruling about the precedents’ themes before they are created, which means that these decisions should be detected through techniques of Similar Case Retrieval, which we tackle from the angle of Case Classification. The contributions of this article are therefore twofold: on the mathematical side, we compare the use of different methods of Natural Language Processing — TF-IDF, LSTM, Longformer, and regex — for Case Classification, whereas on the legal side, we contrast the inefficiency of these binding precedents with a set of hypotheses that may justify their repeated usage. We observe that the TF-IDF models performed slightly better than LSTM and Longformer when compared through common metrics; however, the deep learning models were able to detect certain important legal events that TF-IDF missed. On the legal side, we argue that the reasons for binding precedents to fail in responding to repetitive demand are heterogeneous and case-dependent, making it impossible to single out a specific cause. We identify five main hypotheses, which are found in different combinations in each of the precedents studied.","lang":"eng"}],"oa_version":"Published Version","date_created":"2025-06-15T22:01:31Z","doi":"10.1007/s10506-025-09458-6","article_processing_charge":"Yes (via OA deal)","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s10506-025-09458-6"}],"title":"Empirical analysis of binding precedent efficiency in Brazilian Supreme Court via case classification","department":[{"_id":"UlWa"}],"OA_type":"hybrid","citation":{"chicago":"Tinarrage, Raphaël, Henrique Ennes, Lucas Resck, Lucas T. Gomes, Jean R. Ponciano, and Jorge Poco. “Empirical Analysis of Binding Precedent Efficiency in Brazilian Supreme Court via Case Classification.” <i>Artificial Intelligence and Law</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s10506-025-09458-6\">https://doi.org/10.1007/s10506-025-09458-6</a>.","short":"R. Tinarrage, H. Ennes, L. Resck, L.T. Gomes, J.R. Ponciano, J. Poco, Artificial Intelligence and Law (2025).","ista":"Tinarrage R, Ennes H, Resck L, Gomes LT, Ponciano JR, Poco J. 2025. Empirical analysis of binding precedent efficiency in Brazilian Supreme Court via case classification. Artificial Intelligence and Law.","mla":"Tinarrage, Raphaël, et al. “Empirical Analysis of Binding Precedent Efficiency in Brazilian Supreme Court via Case Classification.” <i>Artificial Intelligence and Law</i>, Springer Nature, 2025, doi:<a href=\"https://doi.org/10.1007/s10506-025-09458-6\">10.1007/s10506-025-09458-6</a>.","apa":"Tinarrage, R., Ennes, H., Resck, L., Gomes, L. T., Ponciano, J. R., &#38; Poco, J. (2025). Empirical analysis of binding precedent efficiency in Brazilian Supreme Court via case classification. <i>Artificial Intelligence and Law</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10506-025-09458-6\">https://doi.org/10.1007/s10506-025-09458-6</a>","ama":"Tinarrage R, Ennes H, Resck L, Gomes LT, Ponciano JR, Poco J. Empirical analysis of binding precedent efficiency in Brazilian Supreme Court via case classification. <i>Artificial Intelligence and Law</i>. 2025. doi:<a href=\"https://doi.org/10.1007/s10506-025-09458-6\">10.1007/s10506-025-09458-6</a>","ieee":"R. Tinarrage, H. Ennes, L. Resck, L. T. Gomes, J. R. Ponciano, and J. Poco, “Empirical analysis of binding precedent efficiency in Brazilian Supreme Court via case classification,” <i>Artificial Intelligence and Law</i>. Springer Nature, 2025."},"publication":"Artificial Intelligence and Law","status":"public","publisher":"Springer Nature","scopus_import":"1","date_updated":"2025-09-30T12:52:15Z","author":[{"last_name":"Tinarrage","first_name":"Raphaël","full_name":"Tinarrage, Raphaël","orcid":"0000-0002-1404-1095","id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e"},{"full_name":"Ennes, Henrique","last_name":"Ennes","first_name":"Henrique"},{"full_name":"Resck, Lucas","last_name":"Resck","first_name":"Lucas"},{"first_name":"Lucas T.","last_name":"Gomes","full_name":"Gomes, Lucas T."},{"last_name":"Ponciano","first_name":"Jean R.","full_name":"Ponciano, Jean R."},{"full_name":"Poco, Jorge","last_name":"Poco","first_name":"Jorge"}],"year":"2025","oa":1,"article_type":"original","quality_controlled":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_place":"publisher","day":"26"},{"oa":1,"quality_controlled":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","alternative_title":["LIPIcs"],"day":"20","volume":332,"scopus_import":"1","has_accepted_license":"1","conference":{"location":"Kanazawa, Japan","name":"SoCG: Symposium on Computational Geometry","start_date":"2025-06-23","end_date":"2025-06-27"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"date_created":"2025-07-14T07:11:04Z","success":1,"access_level":"open_access","date_updated":"2025-07-14T07:11:04Z","file_size":952807,"content_type":"application/pdf","checksum":"a8f7feb1aa3b896e31195841a989d622","relation":"main_file","file_id":"20015","creator":"dernst","file_name":"2025_LIPIcs.SoCG_Streltsova.pdf"}],"ddc":["510"],"OA_type":"gold","citation":{"ama":"Streltsova E, Wagner U. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In: <i> 41st International Symposium on Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">10.4230/LIPIcs.SoCG.2025.75</a>","mla":"Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” <i> 41st International Symposium on Computational Geometry</i>, vol. 332, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">10.4230/LIPIcs.SoCG.2025.75</a>.","apa":"Streltsova, E., &#38; Wagner, U. (2025). Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In <i> 41st International Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>","ieee":"E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers,” in <i> 41st International Symposium on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.","short":"E. Streltsova, U. Wagner, in:,  41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","chicago":"Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” In <i> 41st International Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>.","ista":"Streltsova E, Wagner U. 2025. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers.  41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 75."},"article_number":"75","status":"public","publication":" 41st International Symposium on Computational Geometry","year":"2025","author":[{"full_name":"Streltsova, Elizaveta","last_name":"Streltsova","first_name":"Elizaveta","id":"57a170da-dc96-11ea-b7c8-ab3565071bf7"},{"first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2025-07-14T07:19:19Z","external_id":{"arxiv":["2504.07752","2504.07770"]},"abstract":[{"text":"A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V.\r\nMoreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level).\r\nTo prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope.","lang":"eng"}],"type":"conference","file_date_updated":"2025-07-14T07:11:04Z","arxiv":1,"month":"06","corr_author":"1","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773706"]},"department":[{"_id":"UlWa"}],"article_processing_charge":"Yes","oa_version":"Published Version","doi":"10.4230/LIPIcs.SoCG.2025.75","date_created":"2025-07-13T22:01:22Z","title":"Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"       332","_id":"20004","date_published":"2025-06-20T00:00:00Z"},{"oa":1,"quality_controlled":"1","article_type":"original","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_place":"publisher","day":"15","PlanS_conform":"1","scopus_import":"1","publisher":"Springer Nature","citation":{"mla":"Ennes, Henrique, and Raphaël Tinarrage. “LieDetect: Detection of Representation Orbits of Compact Lie Groups from Point Clouds.” <i>Foundations of Computational Mathematics</i>, Springer Nature, 2025, doi:<a href=\"https://doi.org/10.1007/s10208-025-09728-4\">10.1007/s10208-025-09728-4</a>.","ieee":"H. Ennes and R. Tinarrage, “LieDetect: Detection of representation orbits of compact Lie groups from point clouds,” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2025.","apa":"Ennes, H., &#38; Tinarrage, R. (2025). LieDetect: Detection of representation orbits of compact Lie groups from point clouds. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-025-09728-4\">https://doi.org/10.1007/s10208-025-09728-4</a>","ama":"Ennes H, Tinarrage R. LieDetect: Detection of representation orbits of compact Lie groups from point clouds. <i>Foundations of Computational Mathematics</i>. 2025. doi:<a href=\"https://doi.org/10.1007/s10208-025-09728-4\">10.1007/s10208-025-09728-4</a>","short":"H. Ennes, R. Tinarrage, Foundations of Computational Mathematics (2025).","ista":"Ennes H, Tinarrage R. 2025. LieDetect: Detection of representation orbits of compact Lie groups from point clouds. Foundations of Computational Mathematics.","chicago":"Ennes, Henrique, and Raphaël Tinarrage. “LieDetect: Detection of Representation Orbits of Compact Lie Groups from Point Clouds.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s10208-025-09728-4\">https://doi.org/10.1007/s10208-025-09728-4</a>."},"OA_type":"hybrid","status":"public","publication":"Foundations of Computational Mathematics","year":"2025","author":[{"full_name":"Ennes, Henrique","first_name":"Henrique","last_name":"Ennes"},{"id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","orcid":"0000-0002-1404-1095","first_name":"Raphaël","last_name":"Tinarrage","full_name":"Tinarrage, Raphaël"}],"date_updated":"2025-09-30T14:44:53Z","external_id":{"arxiv":["2309.03086"],"isi":["001571197200001"]},"abstract":[{"text":"We suggest a new algorithm to estimate representations of compact Lie groups from finite samples of their orbits. Different from other reported techniques, our method allows the retrieval of the precise representation type as a direct sum of irreducible representations. Moreover, the knowledge of the representation type permits the reconstruction of its orbit, which is useful for identifying the Lie group that generates the action, from a finite list of candidates. Our algorithm is general for any compact Lie group, but only instantiations for SO(2), T^d, SU(2), and SO(3) are considered. Theoretical guarantees of robustness in terms of Hausdorff and Wasserstein distances are derived. Our tools are drawn from geometric measure theory, computational geometry, and optimization on matrix manifolds. The algorithm is tested for synthetic data up to dimension 32, as well as real-life applications in image analysis, harmonic analysis, density estimation, equivariant neural networks, chemical conformational spaces, and classical mechanics systems, achieving very accurate results.","lang":"eng"}],"month":"09","type":"journal_article","arxiv":1,"corr_author":"1","acknowledgement":"The original work behind this article was developed for HE’s master’s thesis, supervised by RT. We are mostly in debt to César Camacho, who was HE’s co-advisor, as well as the members of the thesis jury, Clément Maria, Eduardo Mendes, and Jameson Cahill, not only for agreeing to evaluate the original work but also for many valuable inputs. Finally, we are indebted to the anonymous reviewers for their important feedback and suggestions. Open access funding provided by Institute of Science and Technology (IST Austria).","publication_identifier":{"eissn":["1615-3383"],"issn":["1615-3375"]},"department":[{"_id":"UlWa"}],"main_file_link":[{"url":"https://doi.org/10.1007/s10208-025-09728-4","open_access":"1"}],"article_processing_charge":"Yes (via OA deal)","oa_version":"Published Version","date_created":"2025-09-28T22:01:27Z","doi":"10.1007/s10208-025-09728-4","title":"LieDetect: Detection of representation orbits of compact Lie groups from point clouds","language":[{"iso":"eng"}],"publication_status":"epub_ahead","isi":1,"_id":"20407","date_published":"2025-09-15T00:00:00Z"},{"ec_funded":1,"has_accepted_license":"1","scopus_import":"1","publisher":"Association for Computing Machinery","file":[{"success":1,"date_created":"2025-07-14T06:42:58Z","date_updated":"2025-07-14T06:42:58Z","access_level":"open_access","checksum":"2c9ae7ad0102c41124976f4cb5182760","file_size":940827,"content_type":"application/pdf","file_id":"20013","relation":"main_file","file_name":"2025_STOC_Avvakumov.pdf","creator":"dernst"}],"conference":{"location":"Prague, Czechia","start_date":"2025-06-23","end_date":"2025-06-27","name":"STOC: Symposium on Theory of Computing"},"status":"public","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","OA_type":"hybrid","page":"72-83","citation":{"chicago":"Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 72–83. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>.","ista":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.","short":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 72–83.","ieee":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of 4-colouring G-colourable graphs,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 72–83.","mla":"Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 72–83, doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>.","apa":"Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., &#38; Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 72–83). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>","ama":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring G-colourable graphs. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:72-83. doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>"},"ddc":["000"],"year":"2025","author":[{"last_name":"Avvakumov","first_name":"Sergey","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7840-5062"},{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek","last_name":"Filakovský","first_name":"Marek"},{"orcid":"0000-0003-1245-3456","id":"ec596741-c539-11ec-b829-c79322a91242","full_name":"Opršal, Jakub","first_name":"Jakub","last_name":"Opršal"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","full_name":"Tasinato, Gianluca","first_name":"Gianluca","last_name":"Tasinato"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"date_updated":"2026-04-07T12:36:50Z","quality_controlled":"1","oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"day":"15","OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"status":"public","id":"20339","relation":"dissertation_contains"}]},"_id":"20008","date_published":"2025-06-15T00:00:00Z","abstract":[{"text":"We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory.","lang":"eng"}],"type":"conference","file_date_updated":"2025-07-14T06:42:58Z","month":"06","project":[{"call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"corr_author":"1","acknowledgement":"This research was supported by the Austrian Science Fund (FWF project P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed by the Ministry of Education, Youth and Sports of the Czech Republic. This project has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.","department":[{"_id":"UlWa"}],"title":"Hardness of 4-colouring G-colourable graphs","article_processing_charge":"Yes (in subscription journal)","doi":"10.1145/3717823.3718154","date_created":"2025-07-13T22:01:23Z","oa_version":"Published Version"},{"language":[{"iso":"eng"}],"publication_status":"published","_id":"20339","related_material":{"record":[{"relation":"part_of_dissertation","id":"20008","status":"public"},{"id":"15168","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"19860"}]},"date_published":"2025-09-10T00:00:00Z","abstract":[{"text":"This thesis investigates the interplay between algebraic and topological methods and combinatorial problems, focusing on approximate graph colourings and mass partitioning. The unifying theme throughout the dissertation is the use of continuous maps and symmetry constraints to extract combinatorial insights.\r\n\r\nWe first explore approximate graph colouring problems and more generally promise constraint satisfaction problems. Using tools from equivariant topology in combination with the general theory of polymorphism of a promise constraint satisfaction problem, we establish hardness for specific types of approximations.\r\n\r\nIn the second part, we address mass partitioning problems, where one seeks to divide geometric objects or measures in Euclidean space into parts of equal size using hyperplanes. Employing techniques from topological combinatorics (configuration space/test map setup and Borsuk–Ulam type theorems), we both obtain a new equipartitioning result in the and provide a fast algorithm for computing equipartitioning of point sets in 3D.\r\n","lang":"eng"}],"type":"dissertation","file_date_updated":"2025-09-11T12:26:14Z","month":"09","publication_identifier":{"issn":["2663-337X"]},"corr_author":"1","department":[{"_id":"GradSch"},{"_id":"UlWa"}],"degree_awarded":"PhD","title":"Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems","article_processing_charge":"No","doi":"10.15479/AT-ISTA-20339","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","oa_version":"Published Version","date_created":"2025-09-10T12:17:55Z","has_accepted_license":"1","publisher":"Institute of Science and Technology Austria","file":[{"checksum":"ae097a515b9bb4d4b025ca854ae2ed76","file_size":2218562,"content_type":"application/x-zip-compressed","date_created":"2025-09-11T12:24:12Z","access_level":"closed","date_updated":"2025-09-11T12:24:12Z","relation":"source_file","file_id":"20344","creator":"gtasinat","file_name":"thesis-source.zip"},{"content_type":"application/pdf","checksum":"04b2e016409e52167ce42b0eef839fbf","file_size":10071982,"date_updated":"2025-09-11T12:26:14Z","access_level":"open_access","date_created":"2025-09-11T12:26:14Z","success":1,"file_name":"2025_Tasinato_Gianluca_Thesis.pdf","creator":"gtasinat","file_id":"20345","relation":"main_file"}],"status":"public","page":"106","citation":{"ama":"Tasinato G. Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20339\">10.15479/AT-ISTA-20339</a>","apa":"Tasinato, G. (2025). <i>Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20339\">https://doi.org/10.15479/AT-ISTA-20339</a>","ieee":"G. Tasinato, “Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems,” Institute of Science and Technology Austria, 2025.","mla":"Tasinato, Gianluca. <i>Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20339\">10.15479/AT-ISTA-20339</a>.","chicago":"Tasinato, Gianluca. “Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20339\">https://doi.org/10.15479/AT-ISTA-20339</a>.","ista":"Tasinato G. 2025. Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. Institute of Science and Technology Austria.","short":"G. Tasinato, Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems, Institute of Science and Technology Austria, 2025."},"ddc":["516"],"year":"2025","author":[{"full_name":"Tasinato, Gianluca","last_name":"Tasinato","first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"}],"date_updated":"2026-04-07T12:36:51Z","oa":1,"tmp":{"image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"alternative_title":["ISTA Thesis"],"day":"10","OA_place":"publisher","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","supervisor":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}]},{"day":"12","OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","article_type":"original","oa":1,"year":"2025","author":[{"full_name":"Aronov, Boris","first_name":"Boris","last_name":"Aronov"},{"full_name":"Basit, Abdul","last_name":"Basit","first_name":"Abdul"},{"last_name":"Ramesh","first_name":"Indu","full_name":"Ramesh, Indu"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","full_name":"Tasinato, Gianluca","last_name":"Tasinato","first_name":"Gianluca"},{"last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2026-04-07T12:36:50Z","scopus_import":"1","publisher":"Springer Nature","status":"public","publication":"Discrete & Computational Geometry","citation":{"ieee":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning points in 3D, and efficiently too,” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2025.","ama":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. Eight-partitioning points in 3D, and efficiently too. <i>Discrete &#38; Computational Geometry</i>. 2025. doi:<a href=\"https://doi.org/10.1007/s00454-025-00739-0\">10.1007/s00454-025-00739-0</a>","apa":"Aronov, B., Basit, A., Ramesh, I., Tasinato, G., &#38; Wagner, U. (2025). Eight-partitioning points in 3D, and efficiently too. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-025-00739-0\">https://doi.org/10.1007/s00454-025-00739-0</a>","mla":"Aronov, Boris, et al. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>Discrete &#38; Computational Geometry</i>, Springer Nature, 2025, doi:<a href=\"https://doi.org/10.1007/s00454-025-00739-0\">10.1007/s00454-025-00739-0</a>.","short":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, Discrete &#38; Computational Geometry (2025).","ista":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2025. Eight-partitioning points in 3D, and efficiently too. Discrete &#38; Computational Geometry.","chicago":"Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s00454-025-00739-0\">https://doi.org/10.1007/s00454-025-00739-0</a>."},"OA_type":"hybrid","department":[{"_id":"UlWa"}],"title":"Eight-partitioning points in 3D, and efficiently too","main_file_link":[{"url":"https://doi.org/10.1007/s00454-025-00739-0","open_access":"1"}],"article_processing_charge":"Yes (via OA deal)","oa_version":"Published Version","date_created":"2025-06-22T22:02:07Z","doi":"10.1007/s00454-025-00739-0","abstract":[{"lang":"eng","text":"An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R^3\r\n consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in R^3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in R^3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in R^3 (with prescribed normal direction of one of the planes) in time O(n^7/3). A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024)."}],"month":"06","arxiv":1,"type":"journal_article","external_id":{"isi":["001506904300001"],"arxiv":["2403.02627"]},"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"acknowledgement":"BA and AB would like to thank William Steiger for insightful initial discussions of the problems addressed in this work. Open Access funding enabled and organized by CAUL and its Member Institutions.","isi":1,"_id":"19860","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"18917"},{"status":"public","relation":"dissertation_contains","id":"20339"}],"link":[{"relation":"erratum","url":"https://doi.org/10.1007/s00454-025-00759-w"}]},"date_published":"2025-06-12T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"epub_ahead"},{"intvolume":"        72","publication_status":"published","language":[{"iso":"eng"}],"date_published":"2024-09-01T00:00:00Z","_id":"13974","isi":1,"related_material":{"record":[{"status":"public","id":"6647","relation":"earlier_version"}]},"acknowledgement":"Part of the research leading to this paper was done during the 16th Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018. We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank Stefan Felsner and Manfred Scheucher for finding, communicating the example from Sect. 3.3, and the kind permission to include their visualization of the point set. We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund (FWF), Project  M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P. Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation (GAČR).","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"external_id":{"arxiv":["1812.04911"],"isi":["001038546500001"]},"project":[{"name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"month":"09","arxiv":1,"type":"journal_article","abstract":[{"lang":"eng","text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2."}],"doi":"10.1007/s00454-023-00532-x","oa_version":"Preprint","date_created":"2023-08-06T22:01:12Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1812.04911","open_access":"1"}],"article_processing_charge":"No","title":"The crossing Tverberg theorem","department":[{"_id":"UlWa"}],"page":"831-848","citation":{"chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2024. The crossing Tverberg theorem. Discrete and Computational Geometry. 72, 831–848.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry 72 (2024) 831–848.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” <i>Discrete and Computational Geometry</i>, vol. 72. Springer Nature, pp. 831–848, 2024.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2024). The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. 2024;72:831-848. doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>, vol. 72, Springer Nature, 2024, pp. 831–48, doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>."},"OA_type":"green","status":"public","publication":"Discrete and Computational Geometry","publisher":"Springer Nature","scopus_import":"1","date_updated":"2025-04-14T13:52:36Z","author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774"},{"first_name":"Bernd","last_name":"Gärtner","full_name":"Gärtner, Bernd"},{"first_name":"Andrey","last_name":"Kupavskii","full_name":"Kupavskii, Andrey"},{"first_name":"Pavel","last_name":"Valtr","full_name":"Valtr, Pavel"},{"last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"year":"2024","oa":1,"article_type":"original","quality_controlled":"1","volume":72,"OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01"},{"date_published":"2024-02-01T00:00:00Z","isi":1,"_id":"14660","publication_status":"published","intvolume":"        56","language":[{"iso":"eng"}],"article_processing_charge":"Yes (via OA deal)","doi":"10.1112/blms.12965","oa_version":"Published Version","date_created":"2023-12-10T23:00:58Z","title":"Quantitative Steinitz theorem: A polynomial bound","department":[{"_id":"UlWa"}],"corr_author":"1","acknowledgement":"M.N. was supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences aswell as the National Research, Development and Innovation Fund (NRDI) grants K119670 andK131529, and the ÚNKP-22-5 New National Excellence Program of the Ministry for Innovationand Technology from the source of the NRDI as well as the ELTE TKP 2021-NKTA-62 fundingscheme","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"external_id":{"isi":["001113277100001"],"arxiv":["2212.04308"]},"abstract":[{"text":"The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set 𝑆⊂ℝ𝑑, then there are at most 2𝑑 points of 𝑆 whose convex hull contains the origin in the interior. Bárány, Katchalski,and Pach proved the following quantitative version of Steinitz’s theorem. Let 𝑄 be a convex polytope in ℝ𝑑 containing the standard Euclidean unit ball 𝐁𝑑. Then there exist at most 2𝑑 vertices of 𝑄 whose convex hull 𝑄′ satisfies 𝑟𝐁𝑑⊂𝑄′ with 𝑟⩾𝑑−2𝑑. They conjectured that 𝑟⩾𝑐𝑑−1∕2 holds with a universal constant 𝑐>0. We prove 𝑟⩾15𝑑2, the first polynomial lower bound on 𝑟. Furthermore, we show that 𝑟 is not greater than 2/√𝑑.","lang":"eng"}],"file_date_updated":"2024-07-16T10:35:10Z","arxiv":1,"month":"02","type":"journal_article","date_updated":"2025-09-04T11:31:49Z","year":"2024","author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov","full_name":"Ivanov, Grigory"},{"last_name":"Naszódi","first_name":"Márton","full_name":"Naszódi, Márton"}],"ddc":["510"],"page":"796-802","citation":{"apa":"Ivanov, G., &#38; Naszódi, M. (2024). Quantitative Steinitz theorem: A polynomial bound. <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society. <a href=\"https://doi.org/10.1112/blms.12965\">https://doi.org/10.1112/blms.12965</a>","mla":"Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A Polynomial Bound.” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 2, London Mathematical Society, 2024, pp. 796–802, doi:<a href=\"https://doi.org/10.1112/blms.12965\">10.1112/blms.12965</a>.","ama":"Ivanov G, Naszódi M. Quantitative Steinitz theorem: A polynomial bound. <i>Bulletin of the London Mathematical Society</i>. 2024;56(2):796-802. doi:<a href=\"https://doi.org/10.1112/blms.12965\">10.1112/blms.12965</a>","ieee":"G. Ivanov and M. Naszódi, “Quantitative Steinitz theorem: A polynomial bound,” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 2. London Mathematical Society, pp. 796–802, 2024.","ista":"Ivanov G, Naszódi M. 2024. Quantitative Steinitz theorem: A polynomial bound. Bulletin of the London Mathematical Society. 56(2), 796–802.","chicago":"Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A Polynomial Bound.” <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society, 2024. <a href=\"https://doi.org/10.1112/blms.12965\">https://doi.org/10.1112/blms.12965</a>.","short":"G. Ivanov, M. Naszódi, Bulletin of the London Mathematical Society 56 (2024) 796–802."},"status":"public","publication":"Bulletin of the London Mathematical Society","scopus_import":"1","has_accepted_license":"1","file":[{"success":1,"date_created":"2024-07-16T10:35:10Z","date_updated":"2024-07-16T10:35:10Z","access_level":"open_access","file_size":111756,"content_type":"application/pdf","checksum":"30ea0694757bc668cf7cd15ae357b35e","file_id":"17259","relation":"main_file","file_name":"2024_BulletinLondonMathSoc_Ivanov.pdf","creator":"dernst"}],"publisher":"London Mathematical Society","issue":"2","volume":56,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"quality_controlled":"1","article_type":"original"},{"oa_version":"Published Version","doi":"10.7155/jgaa.v28i2.2988","date_created":"2024-12-01T23:01:54Z","article_processing_charge":"No","title":"Removing popular faces in curve arrangements","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"acknowledgement":"This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. has been supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035] and by the NWO Gravitation project NETWORKS under grant no. 024.002.003. Part of the work was done while A.W. was emplyed at Graz University of Technology. Preliminary versions of this work have been presented at the 38th European Workshop on Computational Geometry (EuroCG\r\n2022) in Perugia [10] and at the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023) in Isola delle Femmine [11].","corr_author":"1","publication_identifier":{"issn":["1526-1719"]},"external_id":{"arxiv":["2202.12175"]},"month":"11","file_date_updated":"2024-12-03T09:45:00Z","type":"journal_article","arxiv":1,"abstract":[{"lang":"eng","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 randomized FPT-time algorithm where the parameter is the number of popular faces."}],"date_published":"2024-11-03T00:00:00Z","_id":"18604","intvolume":"        28","publication_status":"published","DOAJ_listed":"1","language":[{"iso":"eng"}],"issue":"2","volume":28,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","day":"03","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"article_type":"original","quality_controlled":"1","date_updated":"2024-12-03T09:49:18Z","author":[{"full_name":"De Nooijer, Phoebe","last_name":"De Nooijer","first_name":"Phoebe"},{"first_name":"Soeren","last_name":"Terziadis","full_name":"Terziadis, Soeren"},{"last_name":"Weinberger","first_name":"Alexandra","full_name":"Weinberger, Alexandra"},{"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"},{"full_name":"Löffler, Maarten","first_name":"Maarten","last_name":"Löffler"},{"last_name":"Rote","first_name":"Günter","full_name":"Rote, Günter"}],"year":"2024","OA_type":"gold","ddc":["510"],"citation":{"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. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">https://doi.org/10.7155/jgaa.v28i2.2988</a>","ieee":"P. De Nooijer <i>et al.</i>, “Removing popular faces in curve arrangements,” <i>Journal of Graph Algorithms and Applications</i>, vol. 28, no. 2. Brown University, pp. 47–82, 2024.","ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. <i>Journal of Graph Algorithms and Applications</i>. 2024;28(2):47-82. doi:<a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">10.7155/jgaa.v28i2.2988</a>","mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” <i>Journal of Graph Algorithms and Applications</i>, vol. 28, no. 2, Brown University, 2024, pp. 47–82, doi:<a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">10.7155/jgaa.v28i2.2988</a>.","short":"P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, Journal of Graph Algorithms and Applications 28 (2024) 47–82.","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. Journal of Graph Algorithms and Applications. 28(2), 47–82.","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.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2024. <a href=\"https://doi.org/10.7155/jgaa.v28i2.2988\">https://doi.org/10.7155/jgaa.v28i2.2988</a>."},"page":"47-82","status":"public","publication":"Journal of Graph Algorithms and Applications","publisher":"Brown University","file":[{"relation":"main_file","file_id":"18609","creator":"dernst","file_name":"2024_JourGraphAlgorithms_deNooijer.pdf","date_created":"2024-12-03T09:45:00Z","success":1,"access_level":"open_access","date_updated":"2024-12-03T09:45:00Z","content_type":"application/pdf","checksum":"be611da6f9d790dc980d6fb7283fe889","file_size":1582493}],"scopus_import":"1","has_accepted_license":"1"},{"citation":{"ieee":"D. Beďatš, “Separation of variables for scalar-valued polynomials in the non-stable range,” <i>Journal of Algebra</i>, vol. 651. Elsevier, pp. 281–304, 2024.","mla":"Beďatš, Daniel. “Separation of Variables for Scalar-Valued Polynomials in the Non-Stable Range.” <i>Journal of Algebra</i>, vol. 651, Elsevier, 2024, pp. 281–304, doi:<a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">10.1016/j.jalgebra.2024.04.013</a>.","ama":"Beďatš D. Separation of variables for scalar-valued polynomials in the non-stable range. <i>Journal of Algebra</i>. 2024;651:281-304. doi:<a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">10.1016/j.jalgebra.2024.04.013</a>","apa":"Beďatš, D. (2024). Separation of variables for scalar-valued polynomials in the non-stable range. <i>Journal of Algebra</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">https://doi.org/10.1016/j.jalgebra.2024.04.013</a>","chicago":"Beďatš, Daniel. “Separation of Variables for Scalar-Valued Polynomials in the Non-Stable Range.” <i>Journal of Algebra</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.jalgebra.2024.04.013\">https://doi.org/10.1016/j.jalgebra.2024.04.013</a>.","ista":"Beďatš D. 2024. Separation of variables for scalar-valued polynomials in the non-stable range. Journal of Algebra. 651, 281–304.","short":"D. Beďatš, Journal of Algebra 651 (2024) 281–304."},"page":"281-304","ddc":["510"],"OA_type":"hybrid","publication":"Journal of Algebra","status":"public","has_accepted_license":"1","scopus_import":"1","file":[{"file_name":"2024_JourAlgebra_Bedats.pdf","creator":"dernst","file_id":"18638","relation":"main_file","access_level":"open_access","date_updated":"2024-12-09T13:56:26Z","date_created":"2024-12-09T13:56:26Z","success":1,"file_size":486969,"content_type":"application/pdf","checksum":"7b01c89128ba16d5334dfab389a03878"}],"publisher":"Elsevier","date_updated":"2025-09-08T14:57:00Z","year":"2024","author":[{"orcid":"0009-0004-1828-0044","id":"78ea3cc9-31e7-11ee-aa02-a6169bbfe1f1","first_name":"Daniel","last_name":"Beďatš","full_name":"Beďatš, Daniel"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"quality_controlled":"1","article_type":"original","volume":651,"OA_place":"publisher","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"01","publication_status":"published","intvolume":"       651","language":[{"iso":"eng"}],"date_published":"2024-08-01T00:00:00Z","isi":1,"_id":"18617","corr_author":"1","acknowledgement":"The author is sincerely grateful for guidance, advice and valuable feedback from Roman Lávička.","publication_identifier":{"issn":["0021-8693"]},"external_id":{"arxiv":["2309.11154"],"isi":["001232775600001"]},"abstract":[{"text":"Any complex-valued polynomial on (Rn)k decomposes into an algebraic combination of O(n)-invariant polynomials and harmonic polynomials. This decomposition, separation of variables, is granted to be unique if n≥2k−1. We prove that the condition n≥2k−1 is not only sufficient, but also necessary for uniqueness of the separation. Moreover, we describe the structure of non-uniqueness of the separation in the boundary cases when n=2k−2 and n=2k−3.\r\nFormally, we study the kernel of a multiplication map ϕ carrying out separation of variables. We devise a general algorithmic procedure for describing Ker ϕ in the restricted non-stable range k≤n<2k−1. In the full non-stable range n<2k−1, we give formulas for highest weights of generators of the kernel as well as formulas for its Hilbert series. Using the developed methods, we obtain a list of highest weight vectors generating Ker ϕ.","lang":"eng"}],"arxiv":1,"month":"08","file_date_updated":"2024-12-09T13:56:26Z","type":"journal_article","article_processing_charge":"Yes (via OA deal)","oa_version":"Published Version","date_created":"2024-12-04T07:58:45Z","doi":"10.1016/j.jalgebra.2024.04.013","title":"Separation of variables for scalar-valued polynomials in the non-stable range","department":[{"_id":"UlWa"}]},{"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"quality_controlled":"1","volume":293,"OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"06","OA_type":"gold","ddc":["510"],"citation":{"chicago":"Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. “Eight-Partitioning Points in 3D, and Efficiently Too.” In <i>40th International Symposium on Computational Geometry</i>, 293:8:1-8:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>.","ista":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2024. Eight-partitioning points in 3D, and efficiently too. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 293, 8:1-8:15.","short":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15.","apa":"Aronov, B., Basit, A., Ramesh, I., Tasinato, G., &#38; Wagner, U. (2024). Eight-partitioning points in 3D, and efficiently too. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293, p. 8:1-8:15). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>","mla":"Aronov, Boris, et al. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>.","ama":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. Eight-partitioning points in 3D, and efficiently too. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:8:1-8:15. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>","ieee":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning points in 3D, and efficiently too,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293, p. 8:1-8:15."},"page":"8:1-8:15","status":"public","publication":"40th International Symposium on Computational Geometry","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","conference":{"location":"Athens, Greece","start_date":"2024-06-11","end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry"},"file":[{"file_id":"18918","relation":"main_file","file_name":"2024_LIPICs_Aronov.pdf","creator":"dernst","date_created":"2025-01-27T14:17:37Z","success":1,"date_updated":"2025-01-27T14:17:37Z","access_level":"open_access","content_type":"application/pdf","checksum":"443aa29ea5d948e917cfccd681dcf176","file_size":880725}],"scopus_import":"1","has_accepted_license":"1","date_updated":"2026-02-16T12:19:08Z","author":[{"full_name":"Aronov, Boris","first_name":"Boris","last_name":"Aronov"},{"full_name":"Basit, Abdul","last_name":"Basit","first_name":"Abdul"},{"full_name":"Ramesh, Indu","first_name":"Indu","last_name":"Ramesh"},{"full_name":"Tasinato, Gianluca","first_name":"Gianluca","last_name":"Tasinato","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"year":"2024","acknowledgement":"Aronov, Boris: Work has been supported by NSF grants CCF 15-40656 and CCF 20-08551, and by grant 2014/170 from the US-Israel Binational Science Foundation. Part of this research was conducted while BA was visiting ISTA in the summers of 2022 and 2023. The visit of BA to ISTA in the summer of 2022 was supported by an ISTA Visiting Professorship.\r\nBasit, Abdul: Work has been supported by Australian Research Council grant DP220102212.\r\nRamesh, Indu: Work supported by a Tandon School of Engineering Fellowship and by NSF Grant CCF-20-08551.\r\nBA and AB would like to thank William Steiger for insightful initial discussions of the problems addressed in this work.","corr_author":"1","publication_identifier":{"isbn":["9783959773164"]},"external_id":{"arxiv":["2403.02627"]},"arxiv":1,"type":"conference","month":"06","file_date_updated":"2025-01-27T14:17:37Z","abstract":[{"text":"An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument.\r\nWe prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction.\r\nMoreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).","lang":"eng"}],"oa_version":"Published Version","doi":"10.4230/LIPIcs.SoCG.2024.8","date_created":"2025-01-27T14:19:17Z","article_processing_charge":"Yes","title":"Eight-partitioning points in 3D, and efficiently too","department":[{"_id":"UlWa"},{"_id":"GradSch"}],"intvolume":"       293","publication_status":"published","language":[{"iso":"eng"}],"date_published":"2024-06-06T00:00:00Z","_id":"18917","related_material":{"record":[{"relation":"later_version","id":"19860","status":"public"}]}},{"date_published":"2024-01-06T00:00:00Z","_id":"14888","isi":1,"intvolume":"     14466","publication_status":"published","language":[{"iso":"eng"}],"title":"Removing popular faces in curve arrangements","date_created":"2024-01-28T23:01:43Z","doi":"10.1007/978-3-031-49275-4_2","oa_version":"Preprint","article_processing_charge":"No","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2202.12175","open_access":"1"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783031492747"]},"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].","month":"01","arxiv":1,"type":"conference","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"}],"external_id":{"arxiv":["2202.12175"],"isi":["001207942000002"]},"date_updated":"2025-09-04T11:52:35Z","author":[{"full_name":"De Nooijer, Phoebe","first_name":"Phoebe","last_name":"De Nooijer"},{"full_name":"Terziadis, Soeren","first_name":"Soeren","last_name":"Terziadis"},{"full_name":"Weinberger, Alexandra","last_name":"Weinberger","first_name":"Alexandra"},{"last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"first_name":"Tamara","last_name":"Mchedlidze","full_name":"Mchedlidze, Tamara"},{"full_name":"Löffler, Maarten","last_name":"Löffler","first_name":"Maarten"},{"last_name":"Rote","first_name":"Günter","full_name":"Rote, Günter"}],"year":"2024","status":"public","publication":"31st International Symposium on Graph Drawing and Network Visualization","page":"18-33","citation":{"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.","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>","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>.","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>","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.","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.","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>."},"conference":{"location":"Isola delle Femmine, Palermo, Italy","start_date":"2023-09-20","end_date":"2023-09-22","name":"GD: Graph Drawing and Network Visualization"},"publisher":"Springer Nature","scopus_import":"1","volume":14466,"day":"06","alternative_title":["LNCS"],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","oa":1},{"month":"03","type":"conference","abstract":[{"lang":"eng","text":"In this paper we build a constructive algorithm that returns a rectifiable curve that connects two points in a weakly convex set in a Hilbert space. We have proven that this algorithm converges and obtained an estimate on the curve’s length and compare the length of the curve obtained to known results."}],"quality_controlled":"1","publication_identifier":{"issn":["0094-243X"],"eissn":["1551-7616"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"}],"day":"14","oa_version":"None","doi":"10.1063/5.0195908","issue":"1","date_created":"2024-04-07T22:00:55Z","article_processing_charge":"No","title":"A constructive algorithm for building rectifiable curves in weakly convex sets","volume":3030,"language":[{"iso":"eng"}],"publisher":"AIP Publishing","conference":{"location":"Virtual","name":"ICCMSE: International Conference of Computational Methods in Sciences and Engiineering","start_date":"2022-10-26","end_date":"2022-10-29"},"scopus_import":"1","citation":{"chicago":"Lopushanski, Mariana, and Grigory Ivanov. “A Constructive Algorithm for Building Rectifiable Curves in Weakly Convex Sets.” In <i>AIP Conference Proceedings</i>, Vol. 3030. AIP Publishing, 2024. <a href=\"https://doi.org/10.1063/5.0195908\">https://doi.org/10.1063/5.0195908</a>.","ista":"Lopushanski M, Ivanov G. 2024. A constructive algorithm for building rectifiable curves in weakly convex sets. AIP Conference Proceedings. ICCMSE: International Conference of Computational Methods in Sciences and Engiineering vol. 3030, 080002.","short":"M. Lopushanski, G. Ivanov, in:, AIP Conference Proceedings, AIP Publishing, 2024.","mla":"Lopushanski, Mariana, and Grigory Ivanov. “A Constructive Algorithm for Building Rectifiable Curves in Weakly Convex Sets.” <i>AIP Conference Proceedings</i>, vol. 3030, no. 1, 080002, AIP Publishing, 2024, doi:<a href=\"https://doi.org/10.1063/5.0195908\">10.1063/5.0195908</a>.","ama":"Lopushanski M, Ivanov G. A constructive algorithm for building rectifiable curves in weakly convex sets. In: <i>AIP Conference Proceedings</i>. Vol 3030. AIP Publishing; 2024. doi:<a href=\"https://doi.org/10.1063/5.0195908\">10.1063/5.0195908</a>","ieee":"M. Lopushanski and G. Ivanov, “A constructive algorithm for building rectifiable curves in weakly convex sets,” in <i>AIP Conference Proceedings</i>, Virtual, 2024, vol. 3030, no. 1.","apa":"Lopushanski, M., &#38; Ivanov, G. (2024). A constructive algorithm for building rectifiable curves in weakly convex sets. In <i>AIP Conference Proceedings</i> (Vol. 3030). Virtual: AIP Publishing. <a href=\"https://doi.org/10.1063/5.0195908\">https://doi.org/10.1063/5.0195908</a>"},"article_number":"080002","status":"public","publication":"AIP Conference Proceedings","intvolume":"      3030","publication_status":"published","author":[{"full_name":"Lopushanski, Mariana","first_name":"Mariana","last_name":"Lopushanski"},{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov","full_name":"Ivanov, Grigory"}],"year":"2024","_id":"15296","date_published":"2024-03-14T00:00:00Z","date_updated":"2024-04-08T07:40:53Z"},{"has_accepted_license":"1","scopus_import":"1","publisher":"Springer Nature","file":[{"success":1,"date_created":"2024-07-16T10:14:13Z","date_updated":"2024-07-16T10:14:13Z","access_level":"open_access","content_type":"application/pdf","checksum":"9418534ac2f3d6f1f091a8b8ccaed01e","file_size":540981,"relation":"main_file","file_id":"17257","creator":"dernst","file_name":"2024_GeometriaeDedicata_Dymond.pdf"}],"status":"public","publication":"Geometriae Dedicata","OA_type":"hybrid","ddc":["510"],"article_number":"15","citation":{"mla":"Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with Respect to Displacement Equivalence.” <i>Geometriae Dedicata</i>, vol. 218, 15, Springer Nature, 2024, doi:<a href=\"https://doi.org/10.1007/s10711-023-00862-3\">10.1007/s10711-023-00862-3</a>.","ama":"Dymond M, Kaluza V. Divergence of separated nets with respect to displacement equivalence. <i>Geometriae Dedicata</i>. 2024;218. doi:<a href=\"https://doi.org/10.1007/s10711-023-00862-3\">10.1007/s10711-023-00862-3</a>","apa":"Dymond, M., &#38; Kaluza, V. (2024). Divergence of separated nets with respect to displacement equivalence. <i>Geometriae Dedicata</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10711-023-00862-3\">https://doi.org/10.1007/s10711-023-00862-3</a>","ieee":"M. Dymond and V. Kaluza, “Divergence of separated nets with respect to displacement equivalence,” <i>Geometriae Dedicata</i>, vol. 218. Springer Nature, 2024.","short":"M. Dymond, V. Kaluza, Geometriae Dedicata 218 (2024).","ista":"Dymond M, Kaluza V. 2024. Divergence of separated nets with respect to displacement equivalence. Geometriae Dedicata. 218, 15.","chicago":"Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with Respect to Displacement Equivalence.” <i>Geometriae Dedicata</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s10711-023-00862-3\">https://doi.org/10.1007/s10711-023-00862-3</a>."},"year":"2024","author":[{"first_name":"Michael","last_name":"Dymond","full_name":"Dymond, Michael"},{"full_name":"Kaluza, Vojtech","last_name":"Kaluza","first_name":"Vojtech","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","orcid":"0000-0002-2512-8698"}],"date_updated":"2025-04-23T07:37:26Z","quality_controlled":"1","article_type":"original","oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"day":"01","OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":218,"language":[{"iso":"eng"}],"publication_status":"published","intvolume":"       218","pmid":1,"_id":"9651","isi":1,"date_published":"2024-02-01T00:00:00Z","abstract":[{"text":"We introduce a hierachy of equivalence relations on the set of separated nets of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞). Two separated nets are called ϕ-displacement equivalent if, roughly speaking, there is a bijection between them which, for large radii R, displaces points of norm at most R by something of order at most ϕ(R). We show that the spectrum of ϕ-displacement equivalence spans from the established notion of bounded displacement equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation, coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞. We further undertake a comparison of our notion of ϕ-displacement equivalence with previously studied relations on separated nets. Particular attention is given to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz equivalence.","lang":"eng"}],"arxiv":1,"type":"journal_article","file_date_updated":"2024-07-16T10:14:13Z","month":"02","external_id":{"pmid":["38021107"],"arxiv":["2102.13046"],"isi":["001105681500001"]},"publication_identifier":{"eissn":["1572-9168"],"issn":["0046-5755"]},"corr_author":"1","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was started while both authors were employed at the University of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35. It was continued when the first named author was employed at University of Leipzig and the second named author was employed at Institute of Science and Technology of Austria, where he was supported by an IST Fellowship.","department":[{"_id":"UlWa"}],"title":"Divergence of separated nets with respect to displacement equivalence","article_processing_charge":"Yes (via OA deal)","oa_version":"Published Version","doi":"10.1007/s10711-023-00862-3","date_created":"2021-07-14T07:01:27Z"},{"department":[{"_id":"UlWa"}],"article_processing_charge":"No","oa_version":"Published Version","doi":"10.4230/LIPIcs.STACS.2024.34","date_created":"2024-03-24T23:00:59Z","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","project":[{"call_identifier":"FWF","grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"external_id":{"arxiv":["2312.12981"],"isi":["001300393400034"]},"abstract":[{"lang":"eng","text":"A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the \"linearly ordered chromatic number\" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023)."}],"file_date_updated":"2024-03-25T07:44:30Z","month":"03","type":"conference","arxiv":1,"corr_author":"1","acknowledgement":"Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]},"_id":"15168","related_material":{"record":[{"status":"public","id":"20339","relation":"dissertation_contains"}]},"isi":1,"date_published":"2024-03-01T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published","intvolume":"       289","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","alternative_title":["LIPIcs"],"day":"01","volume":289,"oa":1,"quality_controlled":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"year":"2024","author":[{"last_name":"Filakovský","first_name":"Marek","full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Nakajima","first_name":"Tamio Vesa","full_name":"Nakajima, Tamio Vesa"},{"id":"ec596741-c539-11ec-b829-c79322a91242","orcid":"0000-0003-1245-3456","first_name":"Jakub","last_name":"Opršal","full_name":"Opršal, Jakub"},{"full_name":"Tasinato, Gianluca","last_name":"Tasinato","first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli"}],"date_updated":"2026-04-07T12:36:50Z","ec_funded":1,"scopus_import":"1","has_accepted_license":"1","file":[{"date_created":"2024-03-25T07:44:30Z","success":1,"date_updated":"2024-03-25T07:44:30Z","access_level":"open_access","checksum":"0524d4189fd1ed08989546511343edf3","content_type":"application/pdf","file_size":927290,"relation":"main_file","file_id":"15175","creator":"dernst","file_name":"2024_LIPICs_Filakovsky.pdf"}],"conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","end_date":"2024-03-14","start_date":"2024-03-12","location":"Clermont-Ferrand, France"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_number":"34","citation":{"apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In <i>41st International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>.","ieee":"M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Clermont-Ferrand, France, 2024, vol. 289.","ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: <i>41st International Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>","chicago":"Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"ddc":["510"],"status":"public","publication":"41st International Symposium on Theoretical Aspects of Computer Science"},{"intvolume":"        69","publication_status":"published","language":[{"iso":"eng"}],"date_published":"2023-04-01T00:00:00Z","isi":1,"_id":"11999","acknowledgement":"This work was started during the 6th Austrian–Japanese–Mexican–Spanish Workshop on Discrete Geometry in June 2019 in Austria. We thank all the participants for the good atmosphere as well as discussions on the topic. Also, we thank Jan Kynčl for sending us remarks on a preliminary version of this work and an anonymous referee for further helpful comments.Alan Arroyo was funded by the Marie Skłodowska-Curie grant agreement No 754411. Fabian Klute was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and by the Austrian Science Fund (FWF): J-4510. Irene Parada and Birgit Vogtenhuber were partially supported by the Austrian Science Fund (FWF): W1230 and within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. Irene Parada was also partially supported by the Independent Research Fund Denmark grant 2020-2023 (9131-00044B) Dynamic Network Analysis and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). Tilo Wiedera was supported by the German Research Foundation (DFG) grant CH 897/2-2.","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"external_id":{"isi":["000840292800001"],"arxiv":["1909.07347"]},"project":[{"call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"file_date_updated":"2022-08-29T11:23:15Z","month":"04","arxiv":1,"type":"journal_article","abstract":[{"lang":"eng","text":"A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles."}],"date_created":"2022-08-28T22:02:01Z","doi":"10.1007/s00454-022-00394-9","oa_version":"Published Version","article_processing_charge":"Yes (in subscription journal)","title":"Inserting one edge into a simple drawing is hard","department":[{"_id":"UlWa"}],"ddc":["510"],"page":"745–770","citation":{"ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” <i>Discrete and Computational Geometry</i>, vol. 69. Springer Nature, pp. 745–770, 2023.","apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Vogtenhuber, B., Seidel, R., &#38; Wiedera, T. (2023). Inserting one edge into a simple drawing is hard. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00394-9\">https://doi.org/10.1007/s00454-022-00394-9</a>","ama":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. Inserting one edge into a simple drawing is hard. <i>Discrete and Computational Geometry</i>. 2023;69:745–770. doi:<a href=\"https://doi.org/10.1007/s00454-022-00394-9\">10.1007/s00454-022-00394-9</a>","mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Discrete and Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 745–770, doi:<a href=\"https://doi.org/10.1007/s00454-022-00394-9\">10.1007/s00454-022-00394-9</a>.","chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Birgit Vogtenhuber, Raimund Seidel, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00394-9\">https://doi.org/10.1007/s00454-022-00394-9</a>.","ista":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. 2023. Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. 69, 745–770.","short":"A.M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, T. Wiedera, Discrete and Computational Geometry 69 (2023) 745–770."},"publication":"Discrete and Computational Geometry","status":"public","file":[{"creator":"alisjak","file_name":"2022_DiscreteandComputionalGeometry_Arroyo.pdf","relation":"main_file","file_id":"12006","date_updated":"2022-08-29T11:23:15Z","access_level":"open_access","date_created":"2022-08-29T11:23:15Z","success":1,"checksum":"def7ae3b28d9fd6aec16450e40090302","content_type":"application/pdf","file_size":1002218}],"publisher":"Springer Nature","scopus_import":"1","has_accepted_license":"1","ec_funded":1,"date_updated":"2025-04-14T07:43:59Z","author":[{"full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Klute","first_name":"Fabian","full_name":"Klute, Fabian"},{"full_name":"Parada, Irene","first_name":"Irene","last_name":"Parada"},{"full_name":"Vogtenhuber, Birgit","first_name":"Birgit","last_name":"Vogtenhuber"},{"full_name":"Seidel, Raimund","first_name":"Raimund","last_name":"Seidel"},{"last_name":"Wiedera","first_name":"Tilo","full_name":"Wiedera, Tilo"}],"year":"2023","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"article_type":"original","quality_controlled":"1","volume":69,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01"}]