2026-09-22T03:57:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26010 2026-09-05T19:34:18Z ddc:004 open_access

A Practical Algorithm for (Geometry-Aware) Interleavings Between Merge Trees Beurskens, Thijs Gæde, Emil Toftegaard Ophelders, Tim Sonke, Willem Speckmann, Bettina Verbeek, Kevin interleaving distance geometry-aware exact algorithm implementation Merge trees are a popular topological descriptor for scalar field data. A common measure to compare two merge trees is the interleaving distance, which relies on a mapping between the two merge trees, also referred to as an interleaving. Despite its desirable properties, the interleaving distance has not been used much in practice, largely due to the fact that computing the exact interleaving distance is NP-hard. In this paper, we show that the exact interleaving distance can be computed efficiently for merge trees encountered in practice: we present the first implementation of the exact fixed-parameter tractable (FPT) algorithm by Touli and Wang [Touli and Wang, 2022]. This algorithm uses a dynamic program to test if a specific interleaving distance δ is feasible. They bound the running time using a parameter τ that captures the number of mapping options between the two merge trees for the output distance δ. Our experiments show that, even though τ can become quite large for real-world merge trees, the running time of our implementation does not depend very heavily on τ. Furthermore, we modify the FPT algorithm into a sweepline algorithm that runs much faster in practice. Finally, we introduce a natural restriction for the interleaving distance capturing the geometric similarity between the underlying scalar fields. This restricted interleaving distance can be computed more efficiently and can, in some settings, also result in more meaningful interleavings. We extend our implementations to support these restrictions and demonstrate their effect on the running time of the algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thijs Beurskens and Emil Toftegaard Gæde and Tim Ophelders and Willem Sonke and Bettina Speckmann and Kevin Verbeek 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.6 urn:nbn:de:0030-drops-260100 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode