Open Collections

Gromov-Hausdorff and Interleaving distance for trees

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Algebraic topology; Statistics

video/mp4

Author affiliation: Ohio State University

2019-03-24

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69161

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/