Locally Correct Interleavings between Merge Trees

Thijs Beurskens, Tim Ophelders, Bettina Speckmann, Kevin Verbeek · 2025

Read Locally Correct Interleavings between Merge Trees by Thijs Beurskens, Tim Ophelders, Bettina Speckmann, Kevin Verbeek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-16474.txt.

Introduction

Thijs Beurskens and three co-authors improve a shape comparison method in a paper that appeared on arXiv in 2025. Sequences of terrains over time, from shifting landscapes to growing data, need compact summaries and fair comparisons. Merge trees summarize a terrain's hills and valleys as a branching structure, and the interleaving distance measures how far apart two such trees are.

An optimal interleaving gives one global shift number, but its matching can ignore local similarities between the trees. The authors define locally correct interleavings, which let the shift vary across the trees to reflect local likeness. A generalized residual interleaving distance, allowing extra constraints on the matching maps, makes the definition work. They prove constructively that a locally correct interleaving always exists. Better matchings mean terrain evolution can be tracked feature by feature, not just scored.

Catalog record

CREATORThijs Beurskens, Tim Ophelders, Bettina Speckmann, Kevin Verbeek
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-16474

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Locally Correct Interleavings between Merge Trees Thijs Beurskens, Tim Ophelders, Bettina Speckmann, Kevin Verbeek Abstract Temporal sequences of terrains arise in various application areas. To analyze them efficiently, one generally needs a suitable abstraction of the data as well as a method to compare and match them over time. In this paper we consider merge trees as a topological descriptor for terrains and the interleaving distance as a method to match and compare them. 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 over time, 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. Department of Mathematics and Computer Science, TU Eindhoven, The [email protected]://orcid.org/0009-0004-1185-1545Supported by the Dutch Research Council (NWO) under project no. OCENW.M20.089. Department of Information and Computing Science, Utrecht University, The Netherlands and Department of Mathematics and Computer Science, TU Eindhoven, The [email protected]://orcid.org/0000-0002-9570-024XSupported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Department of Mathematics and Computer Science, TU Eindhoven, The [email protected]://orcid.org/0000-0002-8514-7858 Department of Mathematics and Computer Science, TU Eindhoven, The [email protected]://orcid.org/0000-0003-3052-4844 Special thanks to Willem Sonke for helpful discussions on the topic of this paper and creating Figure 1 . keywords Interleaving distance, merge trees, local correctness, matchings ccs Theory of computation Computational geometry † † runningauthor: T. Beurskens, T. Ophelders, B. Speckmann, K. Verbeek † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Terrains that vary over time are a common data type in various application areas, such as scientific computing or geographic information science. Typically such data sets are very large; to analyze them efficiently one often needs a compact abstraction that captures salient features. Topological data analysis (TDA) provides several topological descriptors [ 15 ] , such as persistence diagrams, Reeb graphs, and Morse-Smale complexes, that can serve as abstractions for 2D, 3D, or higher-dimensional terrains. In this paper we focus in particular on merge trees , which are graph-based descriptors that encode the evolution of connected components of sublevel or superlevel sets of a terrain (see Figure 1 ). Figure 1: A terrain and its merge tree; leaves and internal vertices represent minima and saddles. To analyze temporal sequences of merge trees one does not only need a compact representation, but also efficient ways to compare and match them over time. For merge trees in particular, several distance measures have been proposed, including the edit distance [ 12 ] , the Wasserstein distance [ 10 ] , and the interleaving distance [ 7 ] . However, a distance measure returns only a numeric value that quantifies the similarity of two merge trees T_{1} and T_{2} . In many application scenarios, we would also like to track the merge trees over time and hence need to understand which parts of T_{1} most closely correspond to parts of T_{2} . That is, we are interested in a matching between T_{1} and T_{2} . The interleaving distance in fact relies on a type of matching between the two trees, the so-called interleaving . An interleaving is a pair of ancestor-preserving maps, one from T_{1} to T_{2} and one from T_{2} to T_{1} , whose compositions send points to ancestors: if a point x of T_{1} is mapped to a point y of T_{2} , then y must be mapped to an ancestor of x , and vice versa. The interleaving distance is the maximum shift —the distance between a point and its image—minimized over all interleavings between the trees. We give exact definitions of the interleaving distance and interleavings in Sections 2 and 3 . Figure 2: Two optimal interleavings between merge trees T_{1} and T_{2} . Intuitively, the right interleaving induces a tighter and more meaningful matching than the left interleaving. Two merge trees typically admit many optimal interleavings. The interleaving distance is a bottleneck measure and hence a given optimal interleaving might be locally quite “loose”: the optimal shift might exceed what is needed and thereby fail to capture local similarities between the trees; see Figure 2 . Inspired by the concept of locally correct Fréchet matchings for curves [ 3 ] , in the following we are hence developing a notion of locally optimal interleavings which allows us to distinguish between “tight” and “loose” optimal interleavings. Contributions. A locally correct Fréchet matching is optimal even when considering any two matched subcurves. This is a desirable feature, however, it cannot be directly reproduced using interleavings. First of all, there might not even be a one-to-one correspondence between the points of T_{1} and T_{2} . Furthermore, two optimal interleavings between different pairs of subtrees do not necessarily combine into an optimal interleaving between the two complete trees. As a first step we hence introduce a novel generalization of the interleaving distance that can handle additional constraints on the maps. Specifically, we aim to use constraints that force a point x to be mapped to an ancestor of a particular point y within the other tree. Over interleavings that satisfy such constraints, we aim to minimize the maximum shift over points x that are either unconstrained or map to a strict ancestor of their corresponding point y . We refer to the resulting distance as the residual interleaving distance . In Section 3 , we provide formal definitions and show that an optimal interleaving exists for any constraints. In Section 4 we then propose a definition for locally correct interleavings that builds upon the residual interleaving distance. Specifically, we define a restriction of an interleaving {\mathcal{I}=(\alpha,\beta)} to two subsets S_{1} of T_{1} and S_{2} of T_{2} as the restriction of \alpha to S_{1} together with the restriction of \beta to S_{2} . We call \mathcal{I} locally correct if it minimizes the residual interleaving distance with respect to any restriction of \mathcal{I} . We constructively prove that a locally correct interleaving always exists. Related work. The interleaving distance between merge trees was defined by Morozov et al. [ 7 ] as a tool to study the stability of merge trees. Agarwal et al. [ 1 ] establish a connection between the interleaving distance

Read the complete text