Scalar Field Comparison through Merge Tree Edit Distances

This thesis studies the comparison of scalar fields in scientific visualization based on so-called edit distances between their merge trees. The merge tree is a topological abstraction of a scalar field that captures the topology of the super- or sublevel sets of the scalar field in an abstract tree structure. The main focus of the thesis is to analyze and improve the stability of merge tree edit distances. Stability of topological abstractions and distances defined on them measures the robustness of the comparison to small-scale perturbations of the scalar field. A new stability model is introduced to identify limitations of established edit distances in a more precise and fine-grained manner than previous approaches. To overcome the identified limitations of established edit distances, several new edit distances are presented which show more stable behavior under small-scale perturbations. The core contribution is the class of deformation-based edit distances. Several variants of this edit distance are presented, which cover a large range of stability and computational complexity. Usually, these two properties are in conflict or traded off against each other. The presented distance measures include the first fully stable edit distance for merge trees, as well as polynomial-time computable methods that form a practical compromise between stability and computational complexity. Furthermore, all new methods improve on existing ones in terms of stability. The stability of these methods is demonstrated by a theoretical analysis and an extensive experimental evaluation. The theoretical and experimental analysis clearly identifies the strengths and limitations of the presented methods. In particular, the experiments show that precise analysis using stable distances is often necessary to obtain meaningful results. Although stable comparison is computationally more expensive, the provided algorithms and implementations enable such analysis for moderately, yet realistically sized datasets. In contrast, established methods fail to provide reliable results in many cases. Lastly, two specific applications of deformation-based edit distances are presented to highlight the practical relevance of the studied methods. As a first application, one of the new distances has been integrated into an established visualization and analysis framework for interpolating merge trees in scalar field ensembles or time series. As the second application, a case study is presented to illustrate the utility of merge tree edit distances in the context of electron density data in chemistry.