Dagstuhl-Seminar — Intractability in Discrete Geometry and Topology

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.