TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 24072

Triangulations in Geometry and Topology

( Feb 11 – Feb 16, 2024 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/24072

Organizers

Contact

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)

Dagstuhl Seminar Wiki

Shared Documents

Schedule

Motivation

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.
Copyright Maike Buchin, Jean Cardinal, Arnaud de Mesmay, and Jonathan Spreer

Participants

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)

Classification
  • Computational Geometry
  • Data Structures and Algorithms
  • Discrete Mathematics

Keywords
  • Triangulations
  • Computational Geometry
  • Geometric Topology