[{"doi":"10.4230/LIPIcs.SoCG.2026.93","quality_controlled":"1","OA_place":"publisher","status":"public","ddc":["500"],"article_number":"93:1-93:22","researchdata_availability":"no","keyword":["Triangulation of manifolds","Simplicial approximation","CW complexes","Delaunay complexes","List homomorphism problem","Topological Data Analysis"],"month":"05","oa_version":"Published Version","conference":{"end_date":"2026-06-05","name":"SoCG: Symposium on Computational Geometry","start_date":"2026-06-02","location":"New Brunswick, NJ, United States"},"scopus_import":"1","file":[{"date_created":"2026-06-22T07:53:13Z","file_id":"22111","date_updated":"2026-06-22T07:53:13Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":1436035,"file_name":"2026_LIPIcSSoCG_Tinarrage.pdf","success":1,"checksum":"a468edad327962309688aa78678138da","creator":"dernst"}],"citation":{"ieee":"R. Tinarrage, “Simplicial approximation to CW complexes with spherical Delaunay triangulations,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","apa":"Tinarrage, R. (2026). Simplicial approximation to CW complexes with spherical Delaunay triangulations. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">https://doi.org/10.4230/LIPIcs.SoCG.2026.93</a>","short":"R. Tinarrage, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Tinarrage R. 2026. Simplicial approximation to CW complexes with spherical Delaunay triangulations. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 367, 93:1-93:22.","mla":"Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 93:1-93:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">10.4230/LIPIcs.SoCG.2026.93</a>.","ama":"Tinarrage R. Simplicial approximation to CW complexes with spherical Delaunay triangulations. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">10.4230/LIPIcs.SoCG.2026.93</a>","chicago":"Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">https://doi.org/10.4230/LIPIcs.SoCG.2026.93</a>."},"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":367,"author":[{"orcid":"0000-0002-1404-1095","id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","first_name":"Raphaël","full_name":"Tinarrage, Raphaël","last_name":"Tinarrage"}],"day":"27","related_material":{"link":[{"relation":"software","url":"https://doi.org/10.5281/zenodo.19251455"}]},"article_processing_charge":"Yes","title":"Simplicial approximation to CW complexes with spherical Delaunay triangulations","das_tickbox":"0","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2026-05-27T00:00:00Z","OA_type":"gold","language":[{"iso":"eng"}],"file_date_updated":"2026-06-22T07:53:13Z","type":"conference","_id":"22000","has_accepted_license":"1","intvolume":"       367","abstract":[{"lang":"eng","text":"Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5."}],"external_id":{"arxiv":["2112.07573"]},"arxiv":1,"publication_identifier":{"isbn":["9783959774185"],"eissn":["1868-8969"]},"publication":"42nd International Symposium on Computational Geometry","date_created":"2026-06-14T22:01:43Z","year":"2026","date_updated":"2026-06-22T11:28:26Z","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"supplementarymaterial":"yes","department":[{"_id":"UlWa"}]},{"publication_status":"published","alternative_title":["ISTA Thesis"],"page":"122","citation":{"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>","short":"C.D. Fillmore, Braiding Geometry and Topology to Study Shapes and Data, Institute of Science and Technology Austria, 2026.","ista":"Fillmore CD. 2026. Braiding geometry and topology to study shapes and data. Institute of Science and Technology Austria.","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>.","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."},"file":[{"content_type":"application/pdf","date_updated":"2026-01-30T11:40:09Z","file_id":"21046","date_created":"2026-01-26T19:44:46Z","file_name":"2025_Fillmore_Christopher_Thesis.pdf","relation":"main_file","file_size":55954297,"access_level":"open_access","checksum":"4c0889130095c31d4e5088c5b8dfd607","creator":"cfillmor"},{"date_updated":"2026-01-26T19:46:20Z","file_id":"21047","date_created":"2026-01-26T19:46:20Z","content_type":"application/x-zip-compressed","relation":"source_file","access_level":"closed","file_size":166080788,"file_name":"Thesis.zip","checksum":"d69afb71d82ab98f856886126ee7303a","creator":"cfillmor"}],"publisher":"Institute of Science and Technology Austria","day":"21","related_material":{"record":[{"id":"20260","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","status":"public","id":"21050"},{"id":"21051","status":"public","relation":"part_of_dissertation"}]},"author":[{"full_name":"Fillmore, Christopher D","last_name":"Fillmore","first_name":"Christopher D","id":"35638A5C-AAC7-11E9-B0BF-5503E6697425"}],"doi":"10.15479/AT-ISTA-21021","OA_place":"publisher","degree_awarded":"PhD","ddc":["514","516"],"status":"public","oa_version":"Published Version","month":"01","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"}],"date_created":"2026-01-20T21:38:40Z","year":"2026","date_updated":"2026-04-07T11:42:49Z","publication_identifier":{"issn":["2663-337X"]},"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","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","oa":1,"department":[{"_id":"GradSch"},{"_id":"HeEd"},{"_id":"UlWa"}],"supervisor":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli"}],"date_published":"2026-01-21T00:00:00Z","title":"Braiding geometry and topology to study shapes and data","article_processing_charge":"No","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file_date_updated":"2026-01-30T11:40:09Z","language":[{"iso":"eng"}],"has_accepted_license":"1","_id":"21021","acknowledged_ssus":[{"_id":"M-Shop"},{"_id":"ScienComp"}],"type":"dissertation"},{"acknowledgement":"We thank Olga Kalinina for feedback on our manuscript, Vsevolod Kuksin for fruitful discussions and Lev Tsarin for participation in the design of our models. This work was supported by Japan Science and Technology Agency as part of Adopting Sustainable Partnerships for Innovative Research Ecosystem, Grant No. JPMJAP24B2 (F.A.K. and L.H.I.), and Fonds Zur Förderung der Wissenschaftlichen Forschung Grant ESP253-B (O.O.B.)","publication_identifier":{"eissn":["1091-6490"]},"date_updated":"2026-05-04T06:57:31Z","year":"2026","date_created":"2026-04-12T22:01:47Z","publication":"Proceedings of the National Academy of Sciences","abstract":[{"text":"How functional protein sequences are distributed in sequence space is fundamentally important for evolutionary theory and protein design, particularly if a large diversity of protein functions are hidden in evolutionarily unexplored areas of the sequence space. However, this question is understudied in part because experimental and computational studies use extant sequences as a starting point to study sequence space. Here, we study whether extant sequences are representative of the entire functional sequence space. Across thousands of protein families from vertebrates and bacteria we calculate the dimensionality and the volume of sequence space occupied by extant homologs. We find that the observed dimensionality and volume of extant sequence space are minuscule, many orders of magnitude smaller than what we estimated using a model of protein evolution. Simulating sequence evolution we then quantify the impact of phylogeny, selection, and epistasis on restricting the evolutionary exploration of sequence space. We find that sequence evolution from a single common ancestor, or a single point of origin in sequence space, is by far the largest limiting factor that reduces the dimensionality and volume of extant sequence space. These results indicate that there are vast areas of functional sequence space that have not been explored in evolution because of the excessive restrictions on natural exploration of the protein sequence space imposed by the point of origin effect. We suggest that protein design methods that rely on extant sequences may be limited in their ability to discover truly novel functions.","lang":"eng"}],"external_id":{"pmid":["41915737"]},"department":[{"_id":"UlWa"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"hybrid","file_date_updated":"2026-05-04T06:46:31Z","language":[{"iso":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)"},"title":"Descent from a common ancestor restricts exploration of protein sequence space","article_processing_charge":"Yes (in subscription journal)","date_published":"2026-04-07T00:00:00Z","pmid":1,"intvolume":"       123","type":"journal_article","_id":"21704","has_accepted_license":"1","citation":{"ista":"Isakova LH, Streltsova E, Bochkareva O, Vlasov PK, Kondrashov F. 2026. Descent from a common ancestor restricts exploration of protein sequence space. Proceedings of the National Academy of Sciences. 123(14), e2532018123.","mla":"Isakova, Lada H., et al. “Descent from a Common Ancestor Restricts Exploration of Protein Sequence Space.” <i>Proceedings of the National Academy of Sciences</i>, vol. 123, no. 14, National Academy of Sciences, 2026, p. e2532018123, doi:<a href=\"https://doi.org/10.1073/pnas.2532018123\">10.1073/pnas.2532018123</a>.","chicago":"Isakova, Lada H., Elizaveta Streltsova, Olga Bochkareva, Peter K. Vlasov, and Fyodor Kondrashov. “Descent from a Common Ancestor Restricts Exploration of Protein Sequence Space.” <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences, 2026. <a href=\"https://doi.org/10.1073/pnas.2532018123\">https://doi.org/10.1073/pnas.2532018123</a>.","ama":"Isakova LH, Streltsova E, Bochkareva O, Vlasov PK, Kondrashov F. Descent from a common ancestor restricts exploration of protein sequence space. <i>Proceedings of the National Academy of Sciences</i>. 2026;123(14):e2532018123. doi:<a href=\"https://doi.org/10.1073/pnas.2532018123\">10.1073/pnas.2532018123</a>","short":"L.H. Isakova, E. Streltsova, O. Bochkareva, P.K. Vlasov, F. Kondrashov, Proceedings of the National Academy of Sciences 123 (2026) e2532018123.","apa":"Isakova, L. H., Streltsova, E., Bochkareva, O., Vlasov, P. K., &#38; Kondrashov, F. (2026). Descent from a common ancestor restricts exploration of protein sequence space. <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.2532018123\">https://doi.org/10.1073/pnas.2532018123</a>","ieee":"L. H. Isakova, E. Streltsova, O. Bochkareva, P. K. Vlasov, and F. Kondrashov, “Descent from a common ancestor restricts exploration of protein sequence space,” <i>Proceedings of the National Academy of Sciences</i>, vol. 123, no. 14. National Academy of Sciences, p. e2532018123, 2026."},"file":[{"relation":"main_file","access_level":"open_access","file_size":3355016,"file_name":"2026_PNAS_Isakova.pdf","date_created":"2026-05-04T06:46:31Z","date_updated":"2026-05-04T06:46:31Z","file_id":"21783","content_type":"application/pdf","creator":"dernst","success":1,"checksum":"11b7a13a359e302498b2367906093a6b"}],"publication_status":"published","page":"e2532018123","scopus_import":"1","author":[{"first_name":"Lada H.","last_name":"Isakova","full_name":"Isakova, Lada H."},{"id":"57a170da-dc96-11ea-b7c8-ab3565071bf7","first_name":"Elizaveta","full_name":"Streltsova, Elizaveta","last_name":"Streltsova"},{"last_name":"Bochkareva","full_name":"Bochkareva, Olga","orcid":"0000-0003-1006-6639","id":"C4558D3C-6102-11E9-A62E-F418E6697425","first_name":"Olga"},{"full_name":"Vlasov, Peter K.","last_name":"Vlasov","first_name":"Peter K."},{"first_name":"Fyodor","id":"44FDEF62-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8243-4694","last_name":"Kondrashov","full_name":"Kondrashov, Fyodor"}],"day":"07","publisher":"National Academy of Sciences","volume":123,"OA_place":"publisher","doi":"10.1073/pnas.2532018123","quality_controlled":"1","article_type":"original","month":"04","oa_version":"Published Version","status":"public","issue":"14","ddc":["570"]},{"month":"04","article_type":"original","oa_version":"Published Version","status":"public","ddc":["510"],"issue":"1","keyword":["Lipschitz","bilipschitz","extension","separated net."],"OA_place":"publisher","license":"https://creativecommons.org/licenses/by-nc/4.0/","quality_controlled":"1","doi":"10.54330/afm.181562","author":[{"first_name":"Michael","full_name":"Dymond, Michael","last_name":"Dymond"},{"full_name":"Kaluza, Vojtech","last_name":"Kaluza","orcid":"0000-0002-2512-8698","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","first_name":"Vojtech"}],"day":"17","project":[{"grant_number":"M03100","_id":"fc35eaa2-9c52-11eb-aca3-88501ab155e9","name":"Spectra and topology of graphs and of simplicial complexes"}],"publisher":"Finnish Mathematical Society","volume":51,"citation":{"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.","short":"M. Dymond, V. Kaluza, Annales Fennici Mathematici 51 (2026) 237–260.","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>","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>","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>.","ista":"Dymond M, Kaluza V. 2026. Extending bilipschitz mappings between separated nets. Annales Fennici Mathematici. 51(1), 237–260.","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>."},"file":[{"file_name":"2026_AnnalesFenniciMath_Dymond.pdf","file_size":342082,"relation":"main_file","access_level":"open_access","content_type":"application/pdf","date_updated":"2026-04-28T12:03:13Z","file_id":"21772","date_created":"2026-04-28T12:03:13Z","creator":"dernst","checksum":"442023926a3803d5d6ca8db8dbc4af1c","success":1}],"publication_status":"published","page":"237-260","scopus_import":"1","intvolume":"        51","type":"journal_article","_id":"21766","has_accepted_license":"1","OA_type":"hybrid","language":[{"iso":"eng"}],"file_date_updated":"2026-04-28T12:03:13Z","article_processing_charge":"Yes (in subscription journal)","title":"Extending bilipschitz mappings between separated nets","tmp":{"image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","short":"CC BY-NC (4.0)","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)"},"date_published":"2026-04-17T00:00:00Z","department":[{"_id":"UlWa"}],"corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"arxiv":1,"publication_identifier":{"issn":["2737-0690"],"eissn":["2737-114X"]},"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].","publication":"Annales Fennici Mathematici","date_created":"2026-04-26T22:01:47Z","year":"2026","date_updated":"2026-04-28T12:06:00Z","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"]}},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"department":[{"_id":"UlWa"}],"abstract":[{"lang":"eng","text":"We prove that every 𝐿-bilipschitz mapping ℤ 2 → ℝ2 canbe extended to a 𝐶(𝐿)-bilipschitz mapping ℝ2 → ℝ2,and we provide a polynomial upper bound for 𝐶(𝐿).Moreover, we extend the result to every separated netin ℝ2 instead of ℤ 2, with the upper bound gaininga polynomial dependence on the separation and netconstants associated to the given separated net. Thisanswers an Oberwolfach question of Navas from 2015and is also a positive solution of the two-dimensionalform of a decades old open (in all dimensions at leasttwo) problem due to Alestalo Trotsenko and Väisälä."}],"external_id":{"arxiv":["2410.22294"]},"arxiv":1,"publication_identifier":{"issn":["0024-6107"],"eissn":["1469-7750"]},"acknowledgement":"The authors wish to thank Professor Leonid Kovalev for a valuable observation on the first versionof this work, which led to improved estimates and cleaner proofs in Section 6. The present workdeveloped from a research visit of Michael Dymond to Vojtěch Kaluža at IST Austria, funded by aLondon Mathematical Society Research in Pairs grant. This work was done whilst Vojtěch Kalužawas fully funded by the Austria Science Fund (FWF) [M 3100-N].","date_created":"2026-05-03T22:01:37Z","publication":"Journal of the London Mathematical Society","year":"2026","date_updated":"2026-05-07T08:29:18Z","type":"journal_article","_id":"21778","has_accepted_license":"1","intvolume":"       113","title":"Planar bilipschitz extension from separated nets","article_processing_charge":"Yes (in subscription journal)","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2026-04-01T00:00:00Z","OA_type":"hybrid","file_date_updated":"2026-05-07T08:27:43Z","language":[{"iso":"eng"}],"publisher":"Wiley","project":[{"_id":"fc35eaa2-9c52-11eb-aca3-88501ab155e9","grant_number":"M03100","name":"Spectra and topology of graphs and of simplicial complexes"}],"volume":113,"author":[{"first_name":"Michael","last_name":"Dymond","full_name":"Dymond, Michael"},{"first_name":"Vojtech","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","orcid":"0000-0002-2512-8698","full_name":"Kaluza, Vojtech","last_name":"Kaluza"}],"day":"01","scopus_import":"1","citation":{"ieee":"M. Dymond and V. Kaluza, “Planar bilipschitz extension from separated nets,” <i>Journal of the London Mathematical Society</i>, vol. 113, no. 4. Wiley, 2026.","ista":"Dymond M, Kaluza V. 2026. Planar bilipschitz extension from separated nets. Journal of the London Mathematical Society. 113(4), e70540.","chicago":"Dymond, Michael, and Vojtech Kaluza. “Planar Bilipschitz Extension from Separated Nets.” <i>Journal of the London Mathematical Society</i>. Wiley, 2026. <a href=\"https://doi.org/10.1112/jlms.70540\">https://doi.org/10.1112/jlms.70540</a>.","mla":"Dymond, Michael, and Vojtech Kaluza. “Planar Bilipschitz Extension from Separated Nets.” <i>Journal of the London Mathematical Society</i>, vol. 113, no. 4, e70540, Wiley, 2026, doi:<a href=\"https://doi.org/10.1112/jlms.70540\">10.1112/jlms.70540</a>.","ama":"Dymond M, Kaluza V. Planar bilipschitz extension from separated nets. <i>Journal of the London Mathematical Society</i>. 2026;113(4). doi:<a href=\"https://doi.org/10.1112/jlms.70540\">10.1112/jlms.70540</a>","apa":"Dymond, M., &#38; Kaluza, V. (2026). Planar bilipschitz extension from separated nets. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70540\">https://doi.org/10.1112/jlms.70540</a>","short":"M. Dymond, V. Kaluza, Journal of the London Mathematical Society 113 (2026)."},"file":[{"date_updated":"2026-05-07T08:27:43Z","file_id":"21836","date_created":"2026-05-07T08:27:43Z","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_size":617569,"file_name":"2026_JourLondonMathSoc_Dymond.pdf","success":1,"checksum":"6dbfc7134f732d17c5c8467843a73e90","creator":"dernst"}],"publication_status":"published","status":"public","issue":"4","ddc":["510"],"article_number":"e70540","month":"04","article_type":"original","oa_version":"Published Version","doi":"10.1112/jlms.70540","quality_controlled":"1","OA_place":"publisher"},{"day":"25","author":[{"first_name":"Anton","full_name":"François, Anton","last_name":"François"},{"id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","first_name":"Raphaël","orcid":"0000-0002-1404-1095","last_name":"Tinarrage","full_name":"Tinarrage, Raphaël"}],"volume":68,"publisher":"Springer Nature","publication_status":"published","citation":{"short":"A. François, R. Tinarrage, Journal of Mathematical Imaging and Vision 68 (2026).","apa":"François, A., &#38; Tinarrage, R. (2026). Train-free segmentation in MRI with cubical persistent homology. <i>Journal of Mathematical Imaging and Vision</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10851-026-01300-1\">https://doi.org/10.1007/s10851-026-01300-1</a>","ista":"François A, Tinarrage R. 2026. Train-free segmentation in MRI with cubical persistent homology. Journal of Mathematical Imaging and Vision. 68(3), 20.","chicago":"François, Anton, and Raphaël Tinarrage. “Train-Free Segmentation in MRI with Cubical Persistent Homology.” <i>Journal of Mathematical Imaging and Vision</i>. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/s10851-026-01300-1\">https://doi.org/10.1007/s10851-026-01300-1</a>.","mla":"François, Anton, and Raphaël Tinarrage. “Train-Free Segmentation in MRI with Cubical Persistent Homology.” <i>Journal of Mathematical Imaging and Vision</i>, vol. 68, no. 3, 20, Springer Nature, 2026, doi:<a href=\"https://doi.org/10.1007/s10851-026-01300-1\">10.1007/s10851-026-01300-1</a>.","ama":"François A, Tinarrage R. Train-free segmentation in MRI with cubical persistent homology. <i>Journal of Mathematical Imaging and Vision</i>. 2026;68(3). doi:<a href=\"https://doi.org/10.1007/s10851-026-01300-1\">10.1007/s10851-026-01300-1</a>","ieee":"A. François and R. Tinarrage, “Train-free segmentation in MRI with cubical persistent homology,” <i>Journal of Mathematical Imaging and Vision</i>, vol. 68, no. 3. Springer Nature, 2026."},"file":[{"checksum":"34080653e0f9c6160856a6bbca9b5248","success":1,"creator":"dernst","content_type":"application/pdf","date_created":"2026-06-10T07:58:58Z","date_updated":"2026-06-10T07:58:58Z","file_id":"21990","file_name":"2026_JourMathImaging_Francois.pdf","relation":"main_file","file_size":6070434,"access_level":"open_access"}],"scopus_import":"1","oa_version":"Published Version","article_type":"original","month":"05","article_number":"20","ddc":["510"],"issue":"3","status":"public","OA_place":"publisher","quality_controlled":"1","doi":"10.1007/s10851-026-01300-1","department":[{"_id":"UlWa"}],"oa":1,"corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2026","date_updated":"2026-06-10T08:00:52Z","date_created":"2026-06-08T08:34:43Z","publication":"Journal of Mathematical Imaging and Vision","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria).","arxiv":1,"publication_identifier":{"eissn":["1573-7683"],"issn":["0924-9907"]},"PlanS_conform":"1","external_id":{"arxiv":["2401.01160"]},"abstract":[{"text":"We investigate a framework for train-free MRI segmentation based on Topological Data Analysis. The pipeline proceeds in three steps, first identifying the whole object to segment via automatic thresholding, then detecting a distinctive subset whose topology is known in advance, and finally deducing the various components of the segmentation. A key ingredient is the extraction of approximate representative cycles from persistence diagrams, which provides an interpretable link between persistent features and anatomical components. To clarify the method’s scope, we make the underlying topological and intensity assumptions explicit, quantify when they hold on real data, and analyze typical failure modes. We evaluate the approach on glioblastoma and on fetal cortical plate segmentation, with comparisons to unsupervised and deep-learning references. By operating without large annotated datasets, the method is well suited to scarce-data settings and provides an interpretable baseline and practical initialization for expert refinement or learning-based pipelines.","lang":"eng"}],"intvolume":"        68","has_accepted_license":"1","type":"journal_article","_id":"21954","language":[{"iso":"eng"}],"file_date_updated":"2026-06-10T07:58:58Z","OA_type":"hybrid","date_published":"2026-05-25T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Train-free segmentation in MRI with cubical persistent homology","article_processing_charge":"Yes (via OA deal)"},{"article_processing_charge":"Yes (via OA deal)","title":"Morse predecomposition of an invariant set","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2025-02-01T00:00:00Z","OA_type":"hybrid","language":[{"iso":"eng"}],"file_date_updated":"2024-11-28T06:52:38Z","_id":"18580","type":"journal_article","has_accepted_license":"1","intvolume":"        24","abstract":[{"lang":"eng","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."}],"external_id":{"isi":["001356000500005"],"arxiv":["2312.08013"]},"arxiv":1,"publication_identifier":{"eissn":["1662-3592"],"issn":["1575-5460"]},"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":"Qualitative Theory of Dynamical Systems","date_created":"2024-11-24T23:01:47Z","date_updated":"2025-04-14T07:54:56Z","year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","oa":1,"department":[{"_id":"UlWa"}],"doi":"10.1007/s12346-024-01144-3","quality_controlled":"1","OA_place":"publisher","status":"public","issue":"1","ddc":["514","510"],"article_number":"5","month":"02","article_type":"original","oa_version":"Published Version","ec_funded":1,"scopus_import":"1","file":[{"creator":"mlipinsk","success":1,"checksum":"73309a57cc798d696caa57b6aa1467d8","file_size":1483668,"access_level":"open_access","relation":"main_file","file_name":"2025_predecomposition.pdf","file_id":"18595","date_updated":"2024-11-28T06:52:38Z","date_created":"2024-11-28T06:52:38Z","content_type":"application/pdf"}],"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.","short":"M. Lipiński, K. Mischaikow, M. Mrozek, Qualitative Theory of Dynamical Systems 24 (2025).","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>","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>.","ista":"Lipiński M, Mischaikow K, Mrozek M. 2025. Morse predecomposition of an invariant set. Qualitative Theory of Dynamical Systems. 24(1), 5.","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>."},"isi":1,"publication_status":"published","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"}],"publisher":"Springer Nature","volume":24,"author":[{"full_name":"Lipiński, Michał","last_name":"Lipiński","orcid":"0000-0001-9789-9750","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e","first_name":"Michał"},{"first_name":"Konstantin","full_name":"Mischaikow, Konstantin","last_name":"Mischaikow"},{"full_name":"Mrozek, Marian","last_name":"Mrozek","first_name":"Marian"}],"day":"01"},{"title":"Empirical analysis of binding precedent efficiency in Brazilian Supreme Court via case classification","article_processing_charge":"Yes (via OA deal)","date_published":"2025-05-26T00:00:00Z","OA_type":"hybrid","language":[{"iso":"eng"}],"type":"journal_article","_id":"19848","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"}],"external_id":{"arxiv":["2407.07004"],"isi":["001494836700001"]},"arxiv":1,"publication_identifier":{"eissn":["1572-8382"],"issn":["0924-8463"]},"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria).","publication":"Artificial Intelligence and Law","date_created":"2025-06-15T22:01:31Z","date_updated":"2026-06-18T08:34:38Z","year":"2025","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"department":[{"_id":"UlWa"}],"quality_controlled":"1","doi":"10.1007/s10506-025-09458-6","OA_place":"publisher","status":"public","main_file_link":[{"url":"https://doi.org/10.1007/s10506-025-09458-6","open_access":"1"}],"ddc":["510"],"month":"05","article_type":"original","oa_version":"Published Version","scopus_import":"1","citation":{"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>","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>.","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.","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>.","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>","short":"R. Tinarrage, H. Ennes, L. Resck, L.T. Gomes, J.R. Ponciano, J. Poco, Artificial Intelligence and Law (2025).","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."},"isi":1,"publication_status":"epub_ahead","publisher":"Springer Nature","author":[{"orcid":"0000-0002-1404-1095","id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","first_name":"Raphaël","full_name":"Tinarrage, Raphaël","last_name":"Tinarrage"},{"first_name":"Henrique","last_name":"Ennes","full_name":"Ennes, Henrique"},{"full_name":"Resck, Lucas","last_name":"Resck","first_name":"Lucas"},{"first_name":"Lucas T.","full_name":"Gomes, Lucas T.","last_name":"Gomes"},{"first_name":"Jean R.","full_name":"Ponciano, Jean R.","last_name":"Ponciano"},{"first_name":"Jorge","last_name":"Poco","full_name":"Poco, Jorge"}],"day":"26"},{"quality_controlled":"1","doi":"10.1007/s00454-025-00739-0","OA_place":"publisher","ddc":["500"],"main_file_link":[{"url":"https://doi.org/10.1007/s00454-025-00739-0","open_access":"1"}],"status":"public","oa_version":"Published Version","article_type":"original","month":"06","scopus_import":"1","publication_status":"epub_ahead","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>","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>.","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>.","ista":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2025. Eight-partitioning points in 3D, and efficiently too. Discrete &#38; Computational Geometry.","short":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, Discrete &#38; Computational Geometry (2025).","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>"},"isi":1,"publisher":"Springer Nature","related_material":{"record":[{"id":"18917","status":"public","relation":"earlier_version"},{"status":"public","relation":"dissertation_contains","id":"20339"}],"link":[{"relation":"erratum","url":"https://doi.org/10.1007/s00454-025-00759-w"}]},"day":"12","author":[{"last_name":"Aronov","full_name":"Aronov, Boris","first_name":"Boris"},{"first_name":"Abdul","last_name":"Basit","full_name":"Basit, Abdul"},{"full_name":"Ramesh, Indu","last_name":"Ramesh","first_name":"Indu"},{"full_name":"Tasinato, Gianluca","last_name":"Tasinato","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca"},{"last_name":"Wagner","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"date_published":"2025-06-12T00:00:00Z","article_processing_charge":"Yes (via OA deal)","title":"Eight-partitioning points in 3D, and efficiently too","language":[{"iso":"eng"}],"OA_type":"hybrid","_id":"19860","type":"journal_article","external_id":{"arxiv":["2403.02627"],"isi":["001506904300001"]},"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)."}],"year":"2025","date_updated":"2026-06-18T18:18:28Z","date_created":"2025-06-22T22:02:07Z","publication":"Discrete & Computational Geometry","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.","arxiv":1,"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"UlWa"}]},{"oa_version":"Published Version","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2025-06-23","end_date":"2025-06-27","location":"Kanazawa, Japan"},"month":"06","article_number":"75","ddc":["510"],"status":"public","OA_place":"publisher","quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2025.75","day":"20","author":[{"id":"57a170da-dc96-11ea-b7c8-ab3565071bf7","first_name":"Elizaveta","full_name":"Streltsova, Elizaveta","last_name":"Streltsova"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner"}],"volume":332,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","alternative_title":["LIPIcs"],"file":[{"content_type":"application/pdf","date_created":"2025-07-14T07:11:04Z","date_updated":"2025-07-14T07:11:04Z","file_id":"20015","file_name":"2025_LIPIcs.SoCG_Streltsova.pdf","relation":"main_file","access_level":"open_access","file_size":952807,"checksum":"a8f7feb1aa3b896e31195841a989d622","success":1,"creator":"dernst"}],"citation":{"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.","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.","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>.","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>.","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>","short":"E. Streltsova, U. Wagner, in:,  41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","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>"},"scopus_import":"1","intvolume":"       332","has_accepted_license":"1","type":"conference","_id":"20004","file_date_updated":"2025-07-14T07:11:04Z","language":[{"iso":"eng"}],"OA_type":"gold","date_published":"2025-06-20T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers","article_processing_charge":"Yes","department":[{"_id":"UlWa"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","year":"2025","date_updated":"2025-07-14T07:19:19Z","date_created":"2025-07-13T22:01:22Z","publication":" 41st International Symposium on Computational Geometry","arxiv":1,"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773706"]},"external_id":{"arxiv":["2504.07752","2504.07770"]},"abstract":[{"lang":"eng","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."}]},{"page":"72-83","publication_status":"published","file":[{"date_created":"2025-07-14T06:42:58Z","date_updated":"2025-07-14T06:42:58Z","file_id":"20013","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":940827,"file_name":"2025_STOC_Avvakumov.pdf","success":1,"checksum":"2c9ae7ad0102c41124976f4cb5182760","creator":"dernst"}],"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>.","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>","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.","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>.","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.","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>","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."},"scopus_import":"1","ec_funded":1,"day":"15","related_material":{"record":[{"id":"20339","status":"public","relation":"dissertation_contains"}]},"author":[{"full_name":"Avvakumov, Sergey","last_name":"Avvakumov","orcid":"0000-0002-7840-5062","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský","full_name":"Filakovský, Marek"},{"orcid":"0000-0003-1245-3456","first_name":"Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","last_name":"Opršal","full_name":"Opršal, Jakub"},{"first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","full_name":"Tasinato, Gianluca","last_name":"Tasinato"},{"last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publisher":"Association for Computing Machinery","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312","call_identifier":"FWF"},{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"}],"OA_place":"publisher","quality_controlled":"1","doi":"10.1145/3717823.3718154","conference":{"end_date":"2025-06-27","start_date":"2025-06-23","name":"STOC: Symposium on Theory of Computing","location":"Prague, Czechia"},"oa_version":"Published Version","month":"06","ddc":["000"],"status":"public","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","date_created":"2025-07-13T22:01:23Z","year":"2025","date_updated":"2026-04-07T12:36:50Z","publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"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.","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"}],"department":[{"_id":"UlWa"}],"corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"file_date_updated":"2025-07-14T06:42:58Z","language":[{"iso":"eng"}],"OA_type":"hybrid","date_published":"2025-06-15T00:00:00Z","article_processing_charge":"Yes (in subscription journal)","title":"Hardness of 4-colouring G-colourable graphs","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","type":"conference","_id":"20008"},{"doi":"10.15479/AT-ISTA-20339","OA_place":"publisher","degree_awarded":"PhD","ddc":["516"],"status":"public","oa_version":"Published Version","month":"09","alternative_title":["ISTA Thesis"],"page":"106","publication_status":"published","file":[{"checksum":"ae097a515b9bb4d4b025ca854ae2ed76","creator":"gtasinat","content_type":"application/x-zip-compressed","date_created":"2025-09-11T12:24:12Z","date_updated":"2025-09-11T12:24:12Z","file_id":"20344","file_name":"thesis-source.zip","relation":"source_file","file_size":2218562,"access_level":"closed"},{"file_size":10071982,"relation":"main_file","access_level":"open_access","file_name":"2025_Tasinato_Gianluca_Thesis.pdf","date_created":"2025-09-11T12:26:14Z","file_id":"20345","date_updated":"2025-09-11T12:26:14Z","content_type":"application/pdf","creator":"gtasinat","success":1,"checksum":"04b2e016409e52167ce42b0eef839fbf"}],"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>","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>.","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.","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>.","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.","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."},"publisher":"Institute of Science and Technology Austria","day":"10","related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"20008"},{"id":"15168","status":"public","relation":"part_of_dissertation"},{"id":"19860","status":"public","relation":"part_of_dissertation"}]},"author":[{"first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","last_name":"Tasinato","full_name":"Tasinato, Gianluca"}],"date_published":"2025-09-10T00:00:00Z","title":"Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems","article_processing_charge":"No","tmp":{"image":"/images/cc_by_nc_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"file_date_updated":"2025-09-11T12:26:14Z","language":[{"iso":"eng"}],"has_accepted_license":"1","type":"dissertation","_id":"20339","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"}],"date_created":"2025-09-10T12:17:55Z","year":"2025","date_updated":"2026-06-18T18:18:27Z","publication_identifier":{"issn":["2663-337X"]},"corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","oa":1,"department":[{"_id":"GradSch"},{"_id":"UlWa"}],"supervisor":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner"}]},{"date_created":"2025-09-28T22:01:27Z","publication":"Foundations of Computational Mathematics","date_updated":"2026-06-18T18:22:42Z","year":"2025","arxiv":1,"publication_identifier":{"issn":["1615-3375"],"eissn":["1615-3383"]},"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).","PlanS_conform":"1","external_id":{"arxiv":["2309.03086"],"isi":["001571197200001"]},"abstract":[{"lang":"eng","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."}],"department":[{"_id":"UlWa"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","oa":1,"language":[{"iso":"eng"}],"OA_type":"hybrid","date_published":"2025-09-15T00:00:00Z","article_processing_charge":"Yes (via OA deal)","title":"LieDetect: Detection of representation orbits of compact Lie groups from point clouds","_id":"20407","type":"journal_article","publication_status":"epub_ahead","citation":{"ista":"Ennes H, Tinarrage R. 2025. LieDetect: Detection of representation orbits of compact Lie groups from point clouds. Foundations of Computational Mathematics.","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>.","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>","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>.","short":"H. Ennes, R. Tinarrage, Foundations of Computational Mathematics (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>","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."},"isi":1,"scopus_import":"1","day":"15","author":[{"first_name":"Henrique","full_name":"Ennes, Henrique","last_name":"Ennes"},{"orcid":"0000-0002-1404-1095","first_name":"Raphaël","id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","full_name":"Tinarrage, Raphaël","last_name":"Tinarrage"}],"publisher":"Springer Nature","OA_place":"publisher","quality_controlled":"1","doi":"10.1007/s10208-025-09728-4","oa_version":"Published Version","month":"09","article_type":"original","ddc":["500"],"main_file_link":[{"url":"https://doi.org/10.1007/s10208-025-09728-4","open_access":"1"}],"status":"public"},{"department":[{"_id":"UlWa"},{"_id":"MaKw"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"Open access funding provided by Copenhagen University.","publication_identifier":{"issn":["0343-6993"]},"arxiv":1,"date_updated":"2025-05-19T14:00:09Z","year":"2025","publication":"Mathematical Intelligencer","date_created":"2024-09-29T22:01:38Z","abstract":[{"lang":"eng","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."}],"external_id":{"isi":["001318056000001"],"arxiv":["2303.09459"]},"intvolume":"        47","type":"journal_article","_id":"18157","has_accepted_license":"1","OA_type":"hybrid","file_date_updated":"2025-04-08T11:17:45Z","language":[{"iso":"eng"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Books, Hallways, and social butterflies: A note on sliding block puzzles","article_processing_charge":"Yes (via OA deal)","date_published":"2025-03-01T00:00:00Z","author":[{"id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","first_name":"Florestan R","last_name":"Brunck","full_name":"Brunck, Florestan R"},{"full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567"}],"day":"01","publisher":"Springer Nature","volume":47,"file":[{"file_name":"2025_MathIntelligencer_Brunck.pdf","file_size":1760643,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_updated":"2025-04-08T11:17:45Z","file_id":"19530","date_created":"2025-04-08T11:17:45Z","creator":"dernst","checksum":"c932ebe45c460d4a73f5b2dcca643db1","success":1}],"citation":{"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.","short":"F.R. Brunck, M.A. Kwan, Mathematical Intelligencer 47 (2025) 52–65.","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>","ista":"Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. 47, 52–65.","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>.","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>.","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>"},"isi":1,"publication_status":"published","page":"52-65","scopus_import":"1","article_type":"original","month":"03","oa_version":"Published Version","status":"public","ddc":["510"],"OA_place":"publisher","doi":"10.1007/s00283-024-10358-x","quality_controlled":"1"},{"external_id":{"isi":["001038546500001"],"arxiv":["1812.04911"]},"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."}],"publication":"Discrete and Computational Geometry","date_created":"2023-08-06T22:01:12Z","date_updated":"2025-04-14T13:52:36Z","year":"2024","arxiv":1,"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"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).","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"department":[{"_id":"UlWa"}],"date_published":"2024-09-01T00:00:00Z","title":"The crossing Tverberg theorem","article_processing_charge":"No","language":[{"iso":"eng"}],"OA_type":"green","_id":"13974","type":"journal_article","intvolume":"        72","scopus_import":"1","publication_status":"published","page":"831-848","citation":{"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>","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry 72 (2024) 831–848.","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>.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2024. The crossing Tverberg theorem. Discrete and Computational Geometry. 72, 831–848.","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>","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>."},"isi":1,"volume":72,"publisher":"Springer Nature","project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","call_identifier":"FWF"}],"day":"01","related_material":{"record":[{"id":"6647","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Fulek, Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Gärtner","full_name":"Gärtner, Bernd","first_name":"Bernd"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"first_name":"Pavel","last_name":"Valtr","full_name":"Valtr, Pavel"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli"}],"doi":"10.1007/s00454-023-00532-x","quality_controlled":"1","OA_place":"repository","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1812.04911"}],"status":"public","oa_version":"Preprint","month":"09","article_type":"original"},{"file":[{"success":1,"checksum":"30ea0694757bc668cf7cd15ae357b35e","creator":"dernst","date_created":"2024-07-16T10:35:10Z","date_updated":"2024-07-16T10:35:10Z","file_id":"17259","content_type":"application/pdf","relation":"main_file","file_size":111756,"access_level":"open_access","file_name":"2024_BulletinLondonMathSoc_Ivanov.pdf"}],"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>","short":"G. Ivanov, M. Naszódi, Bulletin of the London Mathematical Society 56 (2024) 796–802.","ista":"Ivanov G, Naszódi M. 2024. Quantitative Steinitz theorem: A polynomial bound. Bulletin of the London Mathematical Society. 56(2), 796–802.","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>","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>.","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>.","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."},"isi":1,"page":"796-802","publication_status":"published","scopus_import":"1","author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov","full_name":"Ivanov, Grigory"},{"last_name":"Naszódi","full_name":"Naszódi, Márton","first_name":"Márton"}],"day":"01","publisher":"London Mathematical Society","volume":56,"quality_controlled":"1","doi":"10.1112/blms.12965","month":"02","article_type":"original","oa_version":"Published Version","status":"public","issue":"2","ddc":["510"],"publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"arxiv":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","date_created":"2023-12-10T23:00:58Z","publication":"Bulletin of the London Mathematical Society","date_updated":"2025-09-04T11:31:49Z","year":"2024","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"}],"external_id":{"arxiv":["2212.04308"],"isi":["001113277100001"]},"department":[{"_id":"UlWa"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","oa":1,"file_date_updated":"2024-07-16T10:35:10Z","language":[{"iso":"eng"}],"article_processing_charge":"Yes (via OA deal)","title":"Quantitative Steinitz theorem: A polynomial bound","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2024-02-01T00:00:00Z","intvolume":"        56","_id":"14660","type":"journal_article","has_accepted_license":"1"},{"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"]},"arxiv":1,"publication_identifier":{"isbn":["9783031492747"],"eissn":["1611-3349"],"issn":["0302-9743"]},"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].","publication":"31st International Symposium on Graph Drawing and Network Visualization","date_created":"2024-01-28T23:01:43Z","date_updated":"2025-09-04T11:52:35Z","year":"2024","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"article_processing_charge":"No","title":"Removing popular faces in curve arrangements","date_published":"2024-01-06T00:00:00Z","language":[{"iso":"eng"}],"_id":"14888","type":"conference","intvolume":"     14466","scopus_import":"1","isi":1,"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. 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>","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.","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.","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>.","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>","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."},"publication_status":"published","alternative_title":["LNCS"],"page":"18-33","publisher":"Springer Nature","volume":14466,"author":[{"first_name":"Phoebe","last_name":"De Nooijer","full_name":"De Nooijer, Phoebe"},{"first_name":"Soeren","last_name":"Terziadis","full_name":"Terziadis, Soeren"},{"full_name":"Weinberger, Alexandra","last_name":"Weinberger","first_name":"Alexandra"},{"orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová","full_name":"Masárová, Zuzana"},{"last_name":"Mchedlidze","full_name":"Mchedlidze, Tamara","first_name":"Tamara"},{"first_name":"Maarten","full_name":"Löffler, Maarten","last_name":"Löffler"},{"first_name":"Günter","last_name":"Rote","full_name":"Rote, Günter"}],"day":"06","quality_controlled":"1","doi":"10.1007/978-3-031-49275-4_2","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2202.12175"}],"status":"public","month":"01","conference":{"end_date":"2023-09-22","start_date":"2023-09-20","name":"GD: Graph Drawing and Network Visualization","location":"Isola delle Femmine, Palermo, Italy"},"oa_version":"Preprint"},{"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>","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.","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.","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>.","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>.","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>","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."},"file":[{"success":1,"checksum":"0524d4189fd1ed08989546511343edf3","creator":"dernst","date_updated":"2024-03-25T07:44:30Z","file_id":"15175","date_created":"2024-03-25T07:44:30Z","content_type":"application/pdf","file_size":927290,"relation":"main_file","access_level":"open_access","file_name":"2024_LIPICs_Filakovsky.pdf"}],"isi":1,"publication_status":"published","alternative_title":["LIPIcs"],"ec_funded":1,"scopus_import":"1","author":[{"first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek","last_name":"Filakovský"},{"first_name":"Tamio Vesa","last_name":"Nakajima","full_name":"Nakajima, Tamio Vesa"},{"last_name":"Opršal","full_name":"Opršal, Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub","orcid":"0000-0003-1245-3456"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca","last_name":"Tasinato","full_name":"Tasinato, Gianluca"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"day":"01","related_material":{"record":[{"id":"20339","status":"public","relation":"dissertation_contains"}]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"volume":289,"doi":"10.4230/LIPIcs.STACS.2024.34","quality_controlled":"1","month":"03","oa_version":"Published Version","conference":{"location":"Clermont-Ferrand, France","end_date":"2024-03-14","start_date":"2024-03-12","name":"STACS: Symposium on Theoretical Aspects of Computer Science"},"status":"public","ddc":["510"],"article_number":"34","arxiv":1,"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]},"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).","date_created":"2024-03-24T23:00:59Z","publication":"41st International Symposium on Theoretical Aspects of Computer Science","year":"2024","date_updated":"2026-04-07T12:36:50Z","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)."}],"external_id":{"arxiv":["2312.12981"],"isi":["001300393400034"]},"department":[{"_id":"UlWa"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","oa":1,"file_date_updated":"2024-03-25T07:44:30Z","language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2024-03-01T00:00:00Z","intvolume":"       289","type":"conference","_id":"15168","has_accepted_license":"1"},{"language":[{"iso":"eng"}],"doi":"10.1063/5.0195908","quality_controlled":"1","date_published":"2024-03-14T00:00:00Z","title":"A constructive algorithm for building rectifiable curves in weakly convex sets","article_processing_charge":"No","intvolume":"      3030","conference":{"location":"Virtual","end_date":"2022-10-29","name":"ICCMSE: International Conference of Computational Methods in Sciences and Engiineering","start_date":"2022-10-26"},"oa_version":"None","month":"03","article_number":"080002","issue":"1","status":"public","_id":"15296","type":"conference","date_updated":"2024-04-08T07:40:53Z","year":"2024","publication_status":"published","publication":"AIP Conference Proceedings","date_created":"2024-04-07T22:00:55Z","citation":{"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.","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>.","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.","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>","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>.","short":"M. Lopushanski, G. Ivanov, in:, AIP Conference Proceedings, AIP Publishing, 2024.","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>"},"publication_identifier":{"issn":["0094-243X"],"eissn":["1551-7616"]},"scopus_import":"1","abstract":[{"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.","lang":"eng"}],"department":[{"_id":"UlWa"}],"day":"14","author":[{"full_name":"Lopushanski, Mariana","last_name":"Lopushanski","first_name":"Mariana"},{"first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","last_name":"Ivanov"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":3030,"publisher":"AIP Publishing"},{"file_date_updated":"2024-12-03T09:45:00Z","language":[{"iso":"eng"}],"OA_type":"gold","date_published":"2024-11-03T00:00:00Z","title":"Removing popular faces in curve arrangements","article_processing_charge":"No","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"intvolume":"        28","has_accepted_license":"1","type":"journal_article","_id":"18604","publication":"Journal of Graph Algorithms and Applications","date_created":"2024-12-01T23:01:54Z","year":"2024","date_updated":"2024-12-03T09:49:18Z","arxiv":1,"publication_identifier":{"issn":["1526-1719"]},"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].","external_id":{"arxiv":["2202.12175"]},"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."}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","oa":1,"OA_place":"publisher","quality_controlled":"1","doi":"10.7155/jgaa.v28i2.2988","oa_version":"Published Version","month":"11","article_type":"original","issue":"2","ddc":["510"],"status":"public","publication_status":"published","page":"47-82","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>","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.","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>.","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>","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>.","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."},"file":[{"file_name":"2024_JourGraphAlgorithms_deNooijer.pdf","relation":"main_file","access_level":"open_access","file_size":1582493,"content_type":"application/pdf","date_created":"2024-12-03T09:45:00Z","date_updated":"2024-12-03T09:45:00Z","file_id":"18609","creator":"dernst","checksum":"be611da6f9d790dc980d6fb7283fe889","success":1}],"DOAJ_listed":"1","scopus_import":"1","day":"03","author":[{"last_name":"De Nooijer","full_name":"De Nooijer, Phoebe","first_name":"Phoebe"},{"last_name":"Terziadis","full_name":"Terziadis, Soeren","first_name":"Soeren"},{"first_name":"Alexandra","last_name":"Weinberger","full_name":"Weinberger, Alexandra"},{"orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","full_name":"Masárová, Zuzana","last_name":"Masárová"},{"full_name":"Mchedlidze, Tamara","last_name":"Mchedlidze","first_name":"Tamara"},{"full_name":"Löffler, Maarten","last_name":"Löffler","first_name":"Maarten"},{"last_name":"Rote","full_name":"Rote, Günter","first_name":"Günter"}],"volume":28,"publisher":"Brown University"}]