Intrinsic Bottleneck Distance for Merge Trees

2025/09/02 by David Beers, Beers, David, Gillian Grindstaff +1
Mathematics · #55M99 (primary) 51F99 (Secondary) #Algebraic Topology (math.AT) #FOS: Mathematics #Metric Geometry (math.MG) #math.AT #math.MG #msc:51F99 #msc:55M99

paper · pdf · doi:10.48550/arxiv.2509.02755

v2: Reworked the proof of the main theorem (now Theorem 21) after identifying a mistake in the proof of the previous Proposition 21 (the previous Equation (4) is in general false). Added several further results (see especially Corollary 22 and Theorem 23). 20 pages, 4 figures

arxiv created 2026/07/29 · arxiv updated 2026/07/30

Abstract

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 the natural 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 intrinsic metrics \widehatd_I and \widehatd_B realized by infinitesimal path length in merge tree space. This implies that they have the same induced length space, and that in cases where a path is known, the bottleneck distance (which can be computed quickly) can be substituted for the interleaving distance (in general, NP-hard to approximate).

Citations

• Locally Correct Interleavings between Merge Trees
• Relating Interleaving and Fréchet Distances via Ordered Merge Trees
• The fiber of persistent homology for trees
• A Graph-Matching Formulation of the Interleaving Distance between Merge Trees
• Metric Geometry of Spaces of Persistence Diagrams
• Geometry-Aware Merge Tree Comparisons for Time-Varying Data with Interleaving Distances
• From Trees to Barcodes and Back Again II: Combinatorial and Probabilistic Aspects of a Topological Inverse Problem
• From trees to barcodes and back again: theoretical and statistical perspectives
• Stable and consistent density-based clustering via multiparameter persistence
• Local Equivalence of Metrics for Multiparameter Persistence Modules
• Information geometry for phylogenetic trees
• Intrinsic Interleaving Distance for Merge Trees
• FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
• Tropical Geometry of Phylogenetic Tree Space: A Statistical Perspective
• The ℓ^∞-Cophenetic Metric for Phylogenetic Trees as an Interleaving Distance
• The Fiber of the Persistence Map for Functions on the Interval
• Theory of interleavings on categories with a flow
• Local Equivalence and Intrinsic Metrics between Reeb Graphs
• Geometry Helps to Compare Persistence Diagrams
• Computing the Gromov-Hausdorff Distance for Metric Trees
• Decomposition of pointwise finite-dimensional persistence modules
• Fréchet Means for Distributions of Persistence diagrams
• Fréchet Means for Distributions of Persistence Diagrams

Related

• Intrinsic Interleaving Distance for Merge Trees
• The Universal ℓ^p-Metric on Merge Trees
• Relating Interleaving and Fréchet Distances via Ordered Merge Trees
• Locally Correct Interleavings between Merge Trees
• A Graph-Matching Formulation of the Interleaving Distance between Merge Trees