ParkView: Visualizing Monotone Interleavings

Thijs Beurskens TU Eindhoven, Steven van den Broek TU Eindhoven, Arjen Simons TU Eindhoven, Willem Sonke TU Eindhoven, Kevin Verbeek TU Eindhoven, Tim Ophelders TU Eindhoven Utrecht University, Michael Hoffmann ETH Zürich, Bettina Speckmann TU Eindhoven · 2025

Read ParkView: Visualizing Monotone Interleavings by Thijs Beurskens TU Eindhoven, Steven van den Broek TU Eindhoven, Arjen Simons TU Eindhoven, Willem Sonke TU Eindhoven, Kevin Verbeek TU Eindhoven, Tim Ophelders TU Eindhoven Utrecht University, Michael Hoffmann ETH Zürich, Bettina Speckmann TU Eindhoven (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-2501-10728.txt.

Introduction

Thijs Beurskens and co-authors design ParkView, a visual scheme for comparing merge trees. Merge trees summarize scalar fields in topological data analysis, and an interleaving measures how alike two trees are. Monotone interleavings also respect a set order on the leaves, which makes them fit for drawing. Their 2025 paper turns that fit into a full encoding.

ParkView splits both trees into paths and matching branches, and draws the two maps of the interleaving in one schematic view. The authors prove structural facts that keep the encoding sparse and scalable. The result scales to large trees without turning into clutter. Visualization researchers get a clear way to see a complex tree comparison at a glance.

Catalog record

CREATORThijs Beurskens TU Eindhoven, Steven van den Broek TU Eindhoven, Arjen Simons TU Eindhoven, Willem Sonke TU Eindhoven, Kevin Verbeek TU Eindhoven, Tim Ophelders TU Eindhoven Utrecht University, Michael Hoffmann ETH Zürich, Bettina Speckmann TU Eindhoven
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-10728

Browse the full library · About the Tower of Babel

Full text

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

ParkView: Visualizing Monotone Interleavings Thijs Beurskens TU Eindhoven, Steven van den Broek TU Eindhoven, Arjen Simons TU Eindhoven, Willem Sonke TU Eindhoven, Kevin Verbeek TU Eindhoven, Tim Ophelders TU Eindhoven Utrecht University, Michael Hoffmann ETH Zürich, Bettina Speckmann TU Eindhoven Abstract Merge trees are a powerful tool from topological data analysis that is frequently used to analyze scalar fields. The similarity between two merge trees can be captured by an interleaving: a pair of maps between the trees that jointly preserve ancestor relations in the trees. Interleavings can have a complex structure; visualizing them requires a sense of (drawing) order which is not inherent in this purely topological concept. However, in practice it is often desirable to introduce additional geometric constraints, which leads to variants such as labeled or monotone interleavings. Monotone interleavings respect a given order on the leaves of the merge trees and hence have the potential to be visualized in a clear and comprehensive manner. In this paper, we introduce ParkView: a schematic, scalable encoding for monotone interleavings. ParkView captures both maps of the interleaving using an optimal decomposition of both trees into paths and corresponding branches. We prove several structural properties of monotone interleavings, which support a sparse visual encoding using active paths and hedges that can be linked using a maximum of 6 colors for merge trees of arbitrary size. We show how to compute an optimal path-branch decomposition in linear time and illustrate ParkView on a number of real-world datasets. \onlineid 0 \vgtccategory Research \vgtcinsertpkg \teaser ParkView of a monotone interleaving. The merge trees (47 leaves each) are derived from Timesteps 25 (left) and 26 (right) of the Ionization Front dataset [ 2 ] . Each merge tree is decomposed optimally into paths; active paths are indicated by vertical colored line segments. Active paths match via color and x -order to enclosing shapes (hedges) for branches in the other tree. The interleaving maps everything inside a hedge to the corresponding active path (i.e. blue hedge 1 maps to active path 1); hedges and active paths have the same height. Hedges can consist of multiple components (hedge 3), which are connected by a line. The height (cost) \delta of the interleaving corresponds to the amount that the top active path sticks out of the top hedge. \CCScatlist \CCScatTwelve Human-centered computingVisualizationVisualization techniques; \CCScatTwelve NetworksTopology analysis and generation; \CCScatTwelve Theory of computationDesign and analysis of algorithms 1 Introduction At the heart of topological data analysis lie so-called topological descriptors: summaries that identify important features of the data. Topological descriptors are used in various application domains, such as medical imaging [ 24 ] , manufacturing [ 29 ] , and environmental science [ 30 ] . They are generally classified into three types [ 34 ] : set-based descriptors such as persistence diagrams [ 8 ] , complex-based descriptors including Morse-Smale complexes [ 7 ] , and graph-based descriptors such as Reeb graphs [ 3 , 21 ] . (a) Arrows from points to their image [ 17 ] (b) Offset image of tree [ 9 ] (c) Labeling [ 6 ] Figure 3 : Visualizing interleavings. We focus on merge trees, which are a graph-based topological descriptor. A merge tree captures how the critical features of a scalar field—minima, maxima and saddle points—are connected ( \autoref fig:merge-tree-from-data). Merge trees are among the most important tools to support the visualization and analysis of scalar fields. For example, merge trees can be used to track features of a time-varying scalar field [ 22 ] and to summarize [ 36 ] or detect outliers [ 35 ] in an ensemble of time-varying scalar fields. See [ 12 , 13 , 18 , 20 , 32 , 33 ] for some very recent additional examples and the survey by Yan et al. [ 34 ] for an extensive overview of merge trees, and other topological descriptors, and their applications for scientific visualization. Merge trees and interleavings. There are various similarity measures that are used to compare merge trees, such as the merge tree edit distance [ 25 , 26 , 31 ] , the Wasserstein distances for merge trees [ 2 ] , and the merge tree matching distance [ 5 ] . We focus on the interleaving distance [ 9 , 14 , 28 ] that captures how far two merge trees are from being isomorphic. The interleaving distance has desirable mathematical properties, such as stability and universality [ 4 ] . Intuitively, it “weaves” the two trees together via two shift maps that take points from one tree to points a fixed distance higher in the other tree while preserving ancestry. The two maps together form an interleaving. Two identical trees can be woven together with two horizontal maps; the height of an interleaving, which captures the distance between the two merge trees, corresponds to the distance that each shift map has to go up the tree towards the root for two trees that are different from each other. Figure 1 : A 2D scalar field with its minima and saddle points marked (left) and the corresponding merge tree (right) . Computing the interleaving distance is NP-hard [ 1 ] . Furthermore, the interleaving distance is a purely topological concept. In practice, it is often desirable to introduce additional geometric constraints such as labels or orders, since merge trees frequently arise from spatial terrains. In addition, to visualize two merge trees together with an interleaving, one needs some sense of (drawing) order to create a meaningful visualization. The labeled interleaving distance [ 9 ] requires a matching of the two merge trees via labels. If such a labeling exists, then the interleaving can be computed efficiently [ 15 ] . Yan et al. [ 35 ] recently proposed methods to construct geometry-aware labelings and use them to analyze time-varying data. The monotone interleaving distance [ 1 ] requires only a prior ordering on the leaves of the merge trees that respects the tree structure. Given such an ordering, for example based on the spatial structure of the data, the monotone interleaving distance can be computed efficiently [ 1 ] . Formally, a merge tree is a tree T equipped with a function f that assigns a height value to every point of T . We think of T as a topological space; as such, we refer to not just the vertices, but also each point on the interior of an edge, as a point of T . The highest vertex of T is called the root , from which an edge extends upwards to infinity. The height function f has to be continuous, and strictly increasing along each leaf-to-root path of T . An ordered merge tree is a merge tree equipped with a total order \sqsubseteq on its leaves that respects the tree’s structure. The interleaving distance compares two merge trees T and T^{\prime} using \delta -interleavings that consist of two \delta -shift maps . A \delta -shift map \alpha takes points in T and maps them continuously to points in T^{\prime} exactly \delta higher. A \delta -interleaving consists of two \delta -shift maps—a map \alpha from T to T^{\prime} and a map \beta from T^{\prime} to T

Read the complete text