Invited Session Mon.1.H 3005

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

Cluster 2: Combinatorial optimization [...]



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


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


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.


  short term loans . Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.