The mathematical study of fundamental objects such as curves, embedded graphs, surfaces and 3-manifolds has a rich and old history. Research into their algorithmic and combinatorial properties, and underlying computational questions, on the other hand, is still young. From the complexity-theoretic side important open problems are hardness of realizability, fine-grained complexity of distance and similarity measure computations, existence of polynomial-time algorithms for flip distances, or approximability of such distances. Combinatorics and algebra come into play when dealing with associated polyhedral structures such as associahedra and secondary polytopes, and mapping class groups of surfaces. Moreover, applied fields such as trajectory analysis and machine learning yield new questions and perspectives.

Triangulations are partitions of the plane into triangles, or more generally, of a space into simplices, which are required to meet face-to-face. Triangulations are typically constrained to use a given set of points as vertices and are fundamental tools in many applications such as computer graphics or geographic information systems. Alternatively, a triangulation can be defined on a topological space as a simplicial complex together with a homeomorphism from this simplicial complex to the space. These triangulations play an important role in the study of metrics on surfaces. We intend to explore both approaches, as well as the interactions between them, with experts in computational geometry and computational topology. We pinpoint the following lines of research.

• A natural class of triangulations of a given geometric point set is the class of Delaunay triangulations. While these are widely studied, there are still many open questions about generalizations of them, and applying them in the non-Euclidean setting.
• Even triangulations of sets of points in convex position are not completely understood. They can be related to each other by flipping the diagonals of quadrilaterals leading to the definition of the flip graph and a polytope known as the associahedron. One open problem about this flip graph is: can shortest paths in the flip graph be computed in polynomial time?
• Triangulations can also be studied in a purely abstract (or topological) setting: in dimension two, as abstract triangles glued along their edges. In this purely combinatorial generalisation of the above-mentioned geometric situations, very fundamental questions are still unanswered.
• For instance, flip graphs of topological triangulations of surfaces are a key technical component in Teichmüller geometry. They provide a discrete analogue of a metric structure on a surface, on which the group of homeomorphisms acts naturally. Results about (topological) flip graphs translates to advances in geometric group theory and the study of moduli spaces.
• The question of realizability connects the geometric with the abstract setting: Given a topological triangulation of, say, a surface, can it be realized in R3 so that the simplices are realized linearly? This and related questions are notoriously hard. Recent advances in this field include an outcome of a previous Dagstuhl Seminar on this topic. In this iteration, we plan to tackle the exact computational complexity of realizing surfaces in R3.
• Geometric triangulations, typically in R2 or R3, occur in many practical applications, where they need to be compared quantitatively. Distance measures for triangulations are much less explored than in many other settings. Hence, we plan to study efficient measures for comparing geometric triangulations.

Creative Commons BY 4.0

Maike Buchin, Jean Cardinal, Arnaud de Mesmay, and Jonathan Spreer