Efficient Heuristic Algorithms for Interleaving Distance between Merge Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911163420246016 |
|---|---|
| author | Touli, Elena Farahbakhsh Masood, Talha Bin |
| author_facet | Touli, Elena Farahbakhsh Masood, Talha Bin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15687 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Heuristic Algorithms for Interleaving Distance between Merge Trees Touli, Elena Farahbakhsh Masood, Talha Bin Computational Geometry 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. |
| title | Efficient Heuristic Algorithms for Interleaving Distance between Merge Trees |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2509.15687 |