Edit Distance between Merge Trees

Physical phenomena are often modeled as scalar functions. A merge tree is a topological structure which captures the salient features of such scalar functions. Multiple scenarios like periodicity detection and temporal summarization in time-varying scalar functions, symmetry detection in biomolecules, require a way to compare these scalar functions in an intuitive and efficient manner. We present such a measure to compare merge trees based on tree edit distances which can be computed efficiently. We provide intuitive cost models, prove that the measure is a metric, and present applications to time-varying scalar fields, 3D cryo electron microscopy data, and 3D shape data to demonstrate the utility of the edit distance towards a feature-driven analysis of scalar fields.

References:

Raghavendra Sridharamurthy, Talha Bin Masood, Adhitya Kamakshidasan and Vijay Natarajan. Edit distance between merge trees. IEEE Transactions on Visualization and Computer Graphics, 26(3), 2020, 1518-1531.

Link: https://vgl.csa.iisc.ac.in/paper.php?pid=057