DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2026.6

A Practical Algorithm for (Geometry-Aware) Interleavings Between Merge Trees

Authors: Thijs Beurskens, Emil Toftegaard Gæde, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

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.

Cite as

Thijs Beurskens, Emil Toftegaard Gæde, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. A Practical Algorithm for (Geometry-Aware) Interleavings Between Merge Trees. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{beurskens_et_al:LIPIcs.SEA.2026.6,
  author =	{Beurskens, Thijs and G{\ae}de, Emil Toftegaard and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{A Practical Algorithm for (Geometry-Aware) Interleavings Between Merge Trees}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.6},
  URN =		{urn:nbn:de:0030-drops-260100},
  doi =		{10.4230/LIPIcs.SEA.2026.6},
  annote =	{Keywords: interleaving distance, geometry-aware, exact algorithm, implementation}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.11

Locally Correct Interleavings Between Merge Trees

Authors: Thijs Beurskens, Tim Ophelders, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

Merge trees are typically used as a topological summary of scalar fields. To analyze e.g. a time-varying scalar field via its merge tree representation, one needs a suitable method to match and compare two merge trees. We consider the interleaving distance as a method to match and compare merge trees. An interleaving between two merge trees consists of two maps, one in each direction. These maps must satisfy ancestor relations and hence introduce a "shift" between points and their image. An optimal interleaving minimizes the maximum shift; the interleaving distance is the value of this shift. However, to study the evolution of merge trees, we need not only a number but also a meaningful matching between the two trees. The two maps of an optimal interleaving induce a matching, but due to the bottleneck nature of the interleaving distance, this matching fails to capture local similarities between the trees. In this paper we hence propose a notion of local optimality for interleavings. To do so, we define the residual interleaving distance, a generalization of the interleaving distance that allows additional constraints on the maps. This allows us to define locally correct interleavings, which use a range of shifts across the two merge trees that reflect the local similarity well. We give a constructive proof that a locally correct interleaving always exists.

Cite as

Thijs Beurskens, Tim Ophelders, Bettina Speckmann, and Kevin Verbeek. Locally Correct Interleavings Between Merge Trees. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{beurskens_et_al:LIPIcs.SoCG.2026.11,
  author =	{Beurskens, Thijs and Ophelders, Tim and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Locally Correct Interleavings Between Merge Trees}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.11},
  URN =		{urn:nbn:de:0030-drops-258173},
  doi =		{10.4230/LIPIcs.SoCG.2026.11},
  annote =	{Keywords: Interleaving distance, merge trees, local correctness, matchings, topological data analysis}
}

Search Results

Documents authored by Beurskens, Thijs

A Practical Algorithm for (Geometry-Aware) Interleavings Between Merge Trees

Abstract

Cite as

Locally Correct Interleavings Between Merge Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message