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


Please select your role
to obtain appropriate quick-links.
As a LIPIcs/OASIcs author, you will be invited by e-mail to register at the Dagstuhl Submission Server. The server will guide you through the publication workflow. Preliminary information can be found here:
Quick Links

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
Shared Documents
Publications
Schedule
Summary
Show Summary

This seminar was a followup to the Dagstuhl Seminars “Applications of Topology to the Analysis of 1-Dimensional Objects” (17072), “Computation in Low-Dimensional Geometry and Topology” (19352), and “Computation and Reconfiguration in Low-Dimensional Topological Spaces” (22062). The common idea behind all of these seminars is to bring together researchers from different communities (such as computational geometry, graph drawing, or geometric topology) with a shared interest in low-dimensional objects (e.g., curves, embedded graphs, knots, or surfaces). The goal of this approach is to foster collaborative work and synergies: The mathematical study of low-dimensional objects has a rich and old history, but research into their algorithmic and combinatorial properties and the underlying computational questions is still young. This makes for a vibrant research situation, giving strong opportunities for interdisciplinary work involving our multiple communities.

The focus of this Dagstuhl Seminar was placed on triangulations: 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 and their moduli space. The multiple facets of triangulations make them an essential and ubiquitous object of study in the combinatorial, algorithmic, geometric and topological properties of low-dimensional spaces, and thus they constitute a fertile ground for collaborations.

The seminar started with a quick introduction of all the participants, and four keynote talks on different aspects of triangulations.

  • Lionel Pournin gave an overview of flip graphs and their combinatorial and algorithmic properties.
  • Saul Schleimer surveyed the use of triangulations in 3-manifold topology and the numerous computational challenges that arise from them.
  • Linda Kleist presented two snapshots on triangulations, first on the computational complexity of linearly embedding simplicial complexes, and then on some hamiltonicity properties of polytopes arising from flipping triangulations.
  • Mikkel Abrahamsen explained new hardness proofs for algorithmic problems related to packing, covering and partitioning simple polygons with unit squares.

We refer to the abstracts later in this report for more details on these contributions.

These keynote introductory talks were followed with an extended open problem session where we gathered a large collection of open problems. Some of these were circulated in advance of the meeting, many of them were new. The remainder of the week was spent working in small groups actively trying to make progress on the most popular open problems. We made extensive use of the tool “Coauthor,” designed by Erik Demaine (MIT). This allowed for a very efficient recording of the progress made in the different groups. Regular progress reports allowed participants to easily switch between groups during the week, or to start new groups, leading to a very dynamic working environment.

We now quickly survey the different problems that have been worked on during this very productive week:

  • Computational complexity of problems in 3-manifold topology. This group discussed computational complexity for important algorithmic problems from 3-manifold topology. Examples of problems include showing that a knot is ribbon, and testing 0-efficiency in a 3-manifold triangulation (lead: Eric Sedgwick).
  • Veering triangulations and the flip graph. This group studied the effect on flip distances of surface triangulations if a veering structure in the associated layered triangulation is (lead: Saul Schleimer).
  • Flip distances. This group investigated distances in the flip graphs of triangulated convex n-gons or annuli, both theoretically and algorithmically (lead: Jonathan Spreer).
  • Hardness for simple polygons. The group considered NP-hard problems on polygons with holes, and how to show that these are also NP-hard on simple polygons. (lead: Lena Schlipf)
  • Catching balls on Curves. This group considered the problem of characterising curves for which there exist a strategy to catch a ball from any initial configuration. (lead: Maarten Löffler)
  • Computing geodesic paths using edge flips. This group investigated the FlipOut algorithm defined by Crane and Sharp to compute geodesics on intrinsic geometric triangulations and its possible variants. (lead: Hsien-Chih Chang)
  • Rendering a knot without self-intersections. This group focused on using topological data analysis techniques to produce instructive 3D models of link diagrams (lead: Clément Maria)
  • Shortest cycle separating k objects from n − k. This group investigated the complexity of, given a collection of n objects, computing the shortest cycle separating k objects from n − k objects, and how it behaves with respect to the parameter k. This was explored in the setting of the plane with obstacles and then planar graphs with obstacles, with an eye towards separating k handles in graphs embedded on surfaces. (lead: Éric Colin de Verdière)

In summary, this Dagstuhl Seminar provided a very fruitful research environment, allowing participants from very different backgrounds to work together on important open problems. Survey feedback from the participants highlighted how much the emphasis on intensive work in small groups was appreciated. In several of the working groups, significant progress was made, and the results are currently prepared to be submitted for publication. As in the previous meetings, the excellent quality of the Dagstuhl infrastructure and the impeccable support of the Dagstuhl staff provided a seamless experience for all the participants. We are hopeful that this successful experience will lead to follow-up Dagstuhl Seminars on related topics.

Copyright Maike Buchin, Jean Cardinal, Arnaud de Mesmay, and Jonathan Spreer
Motivation
Show 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
Show 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
Seminar 24072
© 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ImprintContactAccessibilityPrivacy