论文标题
合并树的基于变形的编辑距离
A Deformation-based Edit Distance for Merge Trees
论文作者
论文摘要
在科学可视化中，通常通过合并树之间的编辑距离进行比较标量场。典型的任务包括整体分析，特征跟踪，对称性或周期性检测。树编辑距离表示如何通过一系列简单的编辑操作将一棵树转变为另一棵树：重新标记，插入和删除节点。在本文中，我们提出了一组新的编辑操作，直接在合并树上起作用，作为几何或拓扑对象：代表的操作是变形缩回和合并树上的反向转换，与在分支分解树上工作的其他方法相反。我们为新的编辑距离提供了一种四分之一的时间算法，该算法是分支分解独立的，并且在所有合并树的集合上都是指标。
In scientific visualization, scalar fields are often compared through edit distances between their merge trees. Typical tasks include ensemble analysis, feature tracking and symmetry or periodicity detection. Tree edit distances represent how one tree can be transformed into another through a sequence of simple edit operations: relabeling, insertion and deletion of nodes. In this paper, we present a new set of edit operations working directly on the merge tree as an geometrical or topological object: the represented operations are deformation retractions and inverse transformations on merge trees, which stands in contrast to other methods working on branch decomposition trees. We present a quartic time algorithm for the new edit distance, which is branch decomposition-independent and a metric on the set of all merge trees.
