Dagstuhl Seminar 26122
Intractability in Discrete Geometry and Topology
( Mar 15 – Mar 19, 2026 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/26122
Organizers
- Jean Cardinal (ULB - Brussels, BE)
- Hsien-Chih Chang (Dartmouth College - Hanover, US)
- Linda Kleist (Universität Hamburg, DE)
- Jonathan Spreer (University of Sydney, AU)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
The mathematical study of fundamental objects such as curves, embedded graphs, surfaces, and 3-manifolds has a rich and old history. However, the study of their algorithmic and combinatorial properties and the underlying computational questions is still in its infancy. There is a diverse pool of open problems and unanswered questions from the complexity- theoretic side. Examples include the hardness of realizability, the fine-grained complexity of distance and similarity measure computations, the existence of polynomial-time algorithms for flip distances, or the approximability of such distances. When dealing with polyhedral structures associated with geometric or topological objects, methods from Combinatorics and Algebra come into play to analyze structures such as associahedra, secondary polytopes, and mapping class groups of surfaces. Applied fields such as trajectory analysis and machine learning bring new questions and a fresh perspective to the field.
This Dagstuhl Seminar on intractability in discrete geometry and topology will bring together researchers from the fields of computational complexity, computational geometry, topology, discrete geometry, and graph drawing; and will focus on the algorithmic, combinatorial, and computational questions mentioned above. In particular, we will work on the following promising directions:
- Embeddability of simplicial complexes
- Polyhedral realizability of triangulations
- Kissing number of semialgebraic sets
- The recognition of Gabriel graphs
- Reconfiguration problems and flip distances
- ∃ℝ-hardness
- Parameterized hardness of topological problems
- Fine-grained complexity for geometric objects
The structure of the seminar is designed to give participants ample time to work on specific problems in small research groups. The expected outcomes of this seminar are therefore new collaborations leading to joint publications and the development of stronger ties, especially between participants with different backgrounds, that would otherwise be difficult to establish.
Creative Commons BY 4.0
Jean Cardinal, Hsien-Chih Chang, Linda Kleist, and Jonathan Spreer
Please log in to DOOR to see more details.
- Mikkel Abrahamsen (University of Copenhagen, DK) [dblp]
- Hugo Akitaya (University of Massachusetts - Lowell, US) [dblp]
- Robin Belton (Vassar College - Poughkeepsie, US) [dblp]
- Maike Buchin (Ruhr-Universität Bochum, DE) [dblp]
- Rhuaidi Burke (University of Oxford, GB)
- Benjamin Burton (The University of Queensland - Brisbane, AU) [dblp]
- Jean Cardinal (ULB - Brussels, BE) [dblp]
- Hsien-Chih Chang (Dartmouth College - Hanover, US) [dblp]
- Arnaud de Mesmay (CNRS, Université Gustave Eiffel - Marne-la-Vallée, FR) [dblp]
- Alex He (University of Sydney, AU) [dblp]
- Michael Hoffmann (ETH Zürich, CH) [dblp]
- Kristóf Huszár (TU Graz, AT) [dblp]
- Sándor Kisfaludi-Bak (Aalto University, FI) [dblp]
- Linda Kleist (Universität Hamburg, DE) [dblp]
- Maarten Löffler (Utrecht University, NL) [dblp]
- Anna Lubiw (University of Waterloo, CA) [dblp]
- Corentin Lunel (Inria - Montpellier, FR) [dblp]
- Clément Maria (Centre Inria d'Université Côte d'Azur, FR) [dblp]
- Lena Schlipf (Universität Tübingen, DE) [dblp]
- Patrick Schnider (ETH Zürich, CH) [dblp]
- Eric Sedgwick (DePaul University - Chicago, US) [dblp]
- Jonathan Spreer (University of Sydney, AU) [dblp]
- Martin Tancer (Charles University - Prague, CZ) [dblp]
- Lucy Tobin (University of Sydney, AU)
- Torsten Ueckerdt (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Birgit Vogtenhuber (TU Graz, AT) [dblp]
- Carola Wenk (Tulane University - New Orleans, US) [dblp]
- Da Wei Zheng (IST Austria - Klosterneuburg, AT) [dblp]
Related Seminars
- Dagstuhl Seminar 17072: Applications of Topology to the Analysis of 1-Dimensional Objects (2017-02-12 - 2017-02-17) (Details)
- Dagstuhl Seminar 19352: Computation in Low-Dimensional Geometry and Topology (2019-08-25 - 2019-08-30) (Details)
- Dagstuhl Seminar 22062: Computation and Reconfiguration in Low-Dimensional Topological Spaces (2022-02-06 - 2022-02-11) (Details)
- Dagstuhl Seminar 24072: Triangulations in Geometry and Topology (2024-02-11 - 2024-02-16) (Details)
Classification
- Computational Complexity
- Computational Geometry
- Discrete Mathematics
Keywords
- Computational Geometry
- Geometric Topology
- Computational Complexity
