Efficient Heuristic Algorithms for Interleaving Distance between Merge Trees
Preprint
Abstract
Merge trees are fundamental structures in topological data analysis. Interleaving distance is a widely accepted metric for comparing merge trees, with applications in visualization and scientific computing. While a greedy algorithm exists for finding the interleaving distance between labeled merge trees with overlapping labels, computing the interleaving distance between unlabeled trees or labeled trees with disjoint labels remains a significant challenge. In this work, we introduce a novel heuristic algorithm for approximating the interleaving distance between labeled merge trees with partial agreement and disagreement. Our method strategically assigns labels primarily to the leaves of the trees to infer structural correspondence. We also introduce an enhanced version of a previous algorithm that offers improved performance. Both algorithms run in polynomial time and provide practical, efficient alternatives for comparing merge trees, particularly in cases involving unlabeled or structurally diverse data. This work contributes a new direction for merge tree analysis and offers promising tools for real-world applications. We demonstrate this application on the simulation of time-varying electron density.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Intrinsic Interleaving Distance for Merge TreesLa Matematica, 2024
- Deciphering Methylation Effects on S2(ππ*) Internal Conversion in the Simplest Linear α,β-Unsaturated CarbonylThe Journal of Physical Chemistry A, 2023
- The ℓ ∞-Cophenetic Metric for Phylogenetic Trees As an Interleaving Distance2019
- Computational Aspects of the Gromov–Hausdorff Distance and its Application in Non-rigid Shape MatchingDiscrete & Computational Geometry, 2017
- Multiscale Symmetry Detection in Scalar Fields by Clustering ContoursIEEE Transactions on Visualization and Computer Graphics, 2014
- Symmetry in Scalar Field TopologyIEEE Transactions on Visualization and Computer Graphics, 2011
- A survey on tree edit distance and related problemsTheoretical Computer Science, 2005
- Computing contour trees in all dimensionsComputational Geometry, 2003
- Alignment of trees — an alternative to tree editTheoretical Computer Science, 1995
- Some MAX SNP-hard results concerning unordered labeled treesInformation Processing Letters, 1994