BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Gromov-Hausdorff and Interleaving distance for trees Wang, Yusu


The Gromov-Haudorff distance is a common way to measure the distortion between two metric spaces. Given two tree metric spaces (metric trees), it provides a natural distance for them. The merge tree is a simple yet meaningful (topological) summary of a scalar function defined on a domain. There are various ways to define the distance between merge trees, including the so-called interleaving distance between trees. In this talk, I will present an interesting relationship between the Gromov-Hausdorff distance and the interleaving distance. I will then show that these distances are NP-hard to approximate within a certain constant factor. But I will also present a fix-parameter-tractable (FPT) algorithm to compute the interleaving distance. Due to the relation between Gromov-Hausdorff distance and interleaving distances, this also lead to a FPT approximate algorithm for the Gromov-Hausdorff distance between general metric trees.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International