A Deformation-based Edit Distance for Merge Trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916130317139968 |
|---|---|
| author | Wetzels, Florian Garth, Christoph |
| author_facet | Wetzels, Florian Garth, Christoph |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_05850 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Deformation-based Edit Distance for Merge Trees Wetzels, Florian Garth, Christoph Computational Geometry 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. |
| title | A Deformation-based Edit Distance for Merge Trees |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2208.05850 |