Intrinsic Bottleneck Distance for Merge Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912568687198208 |
|---|---|
| author | Beers, David Grindstaff, Gillian |
| author_facet | Beers, David Grindstaff, Gillian |
| contents | Merge trees are a topological descriptor of a filtered space that enriches the degree zero barcode with its merge structure. The space of merge trees comes equipped with an interleaving distance $d_I$, which prompts a naive question: is the interleaving distance between two merge trees equal to the bottleneck distance between their corresponding barcodes? As the map from merge trees to barcodes is not injective, the answer as posed is no, but (as conjectured in Gasparovic et al.) we prove that it is true for the \emph{intrinsic} metrics $\widehat{d}_I$ and $\widehat{d}_B$ realized by infinitesimal path length in merge tree space. This result suggests that in some special cases the bottleneck distance (which can be computed quickly) can be substituted for the interleaving distance (in general, NP-hard). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02755 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Intrinsic Bottleneck Distance for Merge Trees Beers, David Grindstaff, Gillian Algebraic Topology Metric Geometry 55M99 (primary) 51F99 (Secondary) Merge trees are a topological descriptor of a filtered space that enriches the degree zero barcode with its merge structure. The space of merge trees comes equipped with an interleaving distance $d_I$, which prompts a naive question: is the interleaving distance between two merge trees equal to the bottleneck distance between their corresponding barcodes? As the map from merge trees to barcodes is not injective, the answer as posed is no, but (as conjectured in Gasparovic et al.) we prove that it is true for the \emph{intrinsic} metrics $\widehat{d}_I$ and $\widehat{d}_B$ realized by infinitesimal path length in merge tree space. This result suggests that in some special cases the bottleneck distance (which can be computed quickly) can be substituted for the interleaving distance (in general, NP-hard). |
| title | Intrinsic Bottleneck Distance for Merge Trees |
| topic | Algebraic Topology Metric Geometry 55M99 (primary) 51F99 (Secondary) |
| url | https://arxiv.org/abs/2509.02755 |