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.

 

  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.