Physical phenomena in science and engineering are frequently modeled using scalar fields. In scalar field topology, graph-based topological descriptors such as merge trees, contour trees, and Reeb graphs are commonly used to characterize topological changes in the (sub)level sets of scalar fields. One of the biggest challenges and opportunities to advance topology-based visualization is to understand and incorporate uncertainty into such topological descriptors to effectively reason about their underlying data. In this paper, we study a structural average of a set of labeled merge trees and use it to encode uncertainty in data. Specifically, we compute a 1-center tree that minimizes its maximum distance to any other tree in the set under a well-defined metric called the interleaving distance. We provide heuristic strategies that compute structural averages of merge trees whose labels do not fully agree. We further provide an interactive visualization system that resembles a numerical calculator that takes as input a set of merge trees and outputs a tree as their structural average. We also highlight structural similarities between the input and the average and incorporate uncertainty information for visual exploration. We develop a novel measure of uncertainty, referred to as consistency, via a metric-space view of the input trees. Finally, we demonstrate an application of our framework through merge trees that arise from ensembles of scalar fields. Our work is the first to employ interleaving distances and consistency to study a global, mathematically rigorous, structural average of merge trees in the context of uncertainty visualization.
Distances between topological structures. Recently, many metrics have been proposed for merge trees, often by way of a restriction from a metric on the more general Reeb graph @cite_20 @cite_80 @cite_1 @cite_39 @cite_34 @cite_4 @cite_50 @cite_61 @cite_64 . In this paper, we focus on the interleaving distance for labeled merge trees @cite_25 . This distance is an example of an interleaving distance between persistence modules @cite_45 , which is brought to graph-based descriptors such as merge trees @cite_80 and Reeb graphs @cite_1 via category theory @cite_21 @cite_22 .
@cite_61 @cite_64 @cite_4 @cite_22 @cite_21 @cite_1 @cite_39 @cite_45 @cite_50 @cite_80 @cite_34 @cite_25 @cite_20
2895105248 2335518360 2806011050 2148561979 1499561838 2962902468 2056761334 2781831736 2789787607
We consider the problem of assessing the similarity of 3D shapes using Reeb graphs from the standpoint of robustness under perturbations. For this purpose, 3D objects are viewed as spaces endowed with real-valued functions, while the similarity between the resulting Reeb graphs is addressed through a graph edit distance. The cases of smooth functions on manifolds and piecewise linear functions on polyhedra stand out as the most interesting ones. The main contribution of this paper is the introduction of a general edit distance suitable for comparing Reeb graphs in these settings. This edit distance promises to be useful for applications in 3D object retrieval because of its stability properties in the presence of noise. The interleaving distance was originally defined in the field of Topological Data Analysis (TDA) by as a metric on the class of persistence modules parametrized over the real line. subsequently extended the definition to categories of functors on a poset, the objects in these categories being regarded as generalized persistence modules'. These metrics typically depend on the choice of a lax semigroup of endomorphisms of the poset. The purpose of the present paper is to develop a more general framework for the notion of interleaving distance using the theory of actegories'. Specifically, we extend the notion of interleaving distance to arbitrary categories equipped with a flow, i.e. a lax monoidal action by the monoid @math . In this way, the class of objects in such a category acquires the structure of a Lawvere metric space. Functors that are colax @math -equivariant yield maps that are @math -Lipschitz. This leads to concise proofs of various known stability results from TDA, by considering appropriate colax @math -equivariant functors. Along the way, we show that several common metrics, including the Hausdorff distance and the @math -norm, can be realized as interleaving distances in this general perspective. We consider the question of defining interleaving metrics on generalized persistence modules over arbitrary preordered sets. Our constructions are functorial, which implies a form of stability for these metrics. We describe a large class of examples, inverse-image persistence modules, which occur whenever a topological space is mapped to a metric space. Several standard theories of persistence and their stability can be described in this framework. This includes the classical case of sublevelset persistent homology. We introduce a distinction between soft' and hard' stability theorems. While our treatment is direct and elementary, the approach can be explained abstractly in terms of monoidal functors. The Reeb graph is a construction which originated in Morse theory to study a real-valued function defined on a topological space. More recently, it has been used in various applications to study noisy data which creates a desire to define a measure of similarity between these structures. Here, we exploit the fact that the category of Reeb graphs is equivalent to the category of a particular class of cosheaf. Using this equivalency, we can define an interleaving' distance between Reeb graphs which is stable under the perturbation of a function. Along the way, we obtain a natural construction for smoothing a Reeb graph to reduce its topological complexity. The smoothed Reeb graph can be constructed in polynomial time. We propose a metric for Reeb graphs, called the functional distortion distance. Under this distance, the Reeb graph is stable against small changes of input functions. At the same time, it remains discriminative at differentiating input functions. In particular, the main result is that the functional distortion distance between two Reeb graphs is bounded from below by the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions. As an application of our results, we analyze a natural simplification scheme for Reeb graphs, and show that persistent features in Reeb graph remains persistent under simplification. Understanding the stability of important features of the Reeb graph under simplification is an interesting problem on its own right, and critical to the practical usage of Reeb graphs. Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence diagrams of nearby functions are close. However, existing stability results are restricted to the case of continuous functions defined over triangulable spaces. In this paper, we present new stability results that do not suffer from the above restrictions. Furthermore, by working at an algebraic level directly, we make it possible to compare the persistence diagrams of functions defined over different spaces, thus enabling a variety of new applications of the concept of persistence. Along the way, we extend the definition of persistence diagram to a larger setting, introduce the notions of discretization of a persistence module and associated pixelization map, define a proximity measure between persistence modules, and show how to interpolate between persistence modules, thereby lending a more analytic character to this otherwise algebraic setting. We believe these new theoretical concepts and tools shed new light on the theory of persistence, in addition to simplifying proofs and enabling new applications. We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are similar in the supremum norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and universal, meaning that it provides an upper bound to any other stable distance. In contrast, via a specific construction, we show that the interleaving distance and the functional distortion distance on Reeb graphs are not universal. There are many metrics available to compare phylogenetic trees since this is a fundamental task in computational biology. In this paper, we focus on one such metric, the l∞-cophenetic metric introduced by This metric works by representing a phylogenetic tree with n labeled leaves as a point in ( R ^ n(n+1) 2 ) known as the cophenetic vector, then comparing the two resulting Euclidean points using the l∞ distance. Meanwhile, the interleaving distance is a formal categorical construction generalized from the definition of , originally introduced to compare persistence modules arising from the field of topological data analysis. We show that the l∞-cophenetic metric is an example of an interleaving distance. To do this, we define phylogenetic trees as a category of merge trees with some additional structure, namely, labelings on the leaves plus a requirement that morphisms respect these labels. Then we can use the definition of a flow on this category to give an interleaving distance. Finally, we show that, because of the additional structure given by the categories defined, the map sending a labeled merge tree to the cophenetic vector is, in fact, an isometric embedding, thus proving that the l∞-cophenetic metric is an interleaving distance.