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 (UL - Brussels, BE)
- Hsien-Chih Chang (Dartmouth College - Hanover, US)
- Linda Kleist (Universität Potsdam, DE)
- Jonathan Spreer (University of Sydney, AU)
Contact
- Andreas Dolzmann (for scientific matters)
- Christina Schwarz (for administrative matters)
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
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
