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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International