Dagstuhl Seminar 26122
Intractability in Discrete Geometry and Topology
( Mar 15 – Mar 19, 2026 )
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 Seminar Wiki
- Dagstuhl Seminar Wiki (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
- Hugo Akitaya
- Robin Belton
- Maike Buchin
- Rhuaidi Burke
- Benjamin Burton
- Jean Cardinal
- Hsien-Chih Chang
- Arnaud de Mesmay
- Alex He
- Michael Hoffmann
- Kristóf Huszár
- Sándor Kisfaludi-Bak
- Linda Kleist
- Maarten Löffler
- Anna Lubiw
- Corentin Lunel
- Clément Maria
- Lena Schlipf
- Patrick Schnider
- Eric Sedgwick
- Jonathan Spreer
- Martin Tancer
- Lucy Tobin
- Torsten Ueckerdt
- Birgit Vogtenhuber
- Carola Wenk
- Da Wei Zheng
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
