Branch Decomposition-Independent Edit Distances for Merge Trees
- Edit distances between merge trees of scalar fields have many applications in scientific visualization, such as ensemble analysis, feature tracking or symmetry detection. In this paper, we propose branch mappings, a novel approach to the construction of edit mappings for merge trees. Classic edit mappings match nodes or edges of two trees onto each other, and therefore have to either rely on branch decompositions of both trees or have to use auxiliary node properties to determine a matching. In contrast, branch mappings employ branch properties instead of node similarity information, and are independent of predetermined branch decompositions. Especially for topological features, which are typically based on branch properties, this allows a more intuitive distance measure which is also less susceptible to instabilities from small-scale perturbations. For trees with 𝒪(n) nodes, we describe an 𝒪(n4) algorithm for computing optimal branch mappings, which is faster than the only other branch decomposition-independent method in the literature by more than a linear factor. Furthermore, we compare the results of our method on synthetic and real-world examples to demonstrate its practicality and utility.
Author: | Florian WetzelsORCiD, Heike LeitteORCiD, Christoph GarthORCiD |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-80671 |
DOI: | https://doi.org/10.1111/cgf.14547 |
ISSN: | 1467-8659 |
Parent Title (English): | Computer Graphics Forum |
Publisher: | Wiley |
Document Type: | Article |
Language of publication: | English |
Date of Publication (online): | 2024/04/17 |
Year of first Publication: | 2022 |
Publishing Institution: | Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau |
Date of the Publication (Server): | 2024/04/17 |
Issue: | 41/3 |
Page Number: | 12 |
First Page: | 367 |
Last Page: | 378 |
Source: | https://onlinelibrary.wiley.com/doi/10.1111/cgf.14547 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Informatik |
DDC-Cassification: | 0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik |
Collections: | Open-Access-Publikationsfonds |
Licence (German): | Zweitveröffentlichung |