## Invited Session Mon.1.H 3005

#### Monday, 10:30 - 12:00 h, Room: H 3005

**Cluster 2: Combinatorial optimization** [...]

### Triangulations

**Chair: Lionel Pournin**

**Monday, 10:30 - 10:55 h, Room: H 3005, Talk 1**

**Lionel Pournin**

The flip-graph of the 4-dimensional cube is connected

**Abstract:**

Flip-graph connectedness is established for the vertex set of the 4-dimensional cube. This result makes it possible to completely enumerate the triangulations of this vertex set in a reasonable time: it is found that there are 92487256 such triangulations, partitioned into 247451 symmetry classes.

**Monday, 11:00 - 11:25 h, Room: H 3005, Talk 2**

**Felix Schmiedl**

Gromov-Hausdorff distance of finite metric spaces

**Abstract:**

The Gromov-Hausdorff distance of two compact metric spaces is a measure for how far the two spaces are from being isometric. It is a pseudometric on the space of compact metric spaces and has been extensively studied in the field of metric geometry.

In recent years, a lot of attention has been devoted to computational aspects of the Gromov-Hausdorff distance. One of the most active topics is the problem of shape recognition, where the goal is to decide whether two shapes given as polygonal meshes are equivalent under certain invariances.

In this talk, we will investigate the computational complexity of several decision versions of the problem. By relating it to other well known combinatorial optimization problems like the clique and the graph isomorphism problem, we prove that determining the largest subspaces of two finite metric spaces with a fixed upper bound on the Gromov-Hausdorff distance is not in **APX**. Furthermore novel algorithms for the problem will be derived from these results.