Reeb graphs are very popular shape descriptors in computational frameworks as they capture both geometrical properties of the shape, and its topological features. Some different methodologies have been proposed in the literature to estimate the similarity of shapes through the comparison of the associated Reeb graphs. In this context, one of the most important open questions is whether Reeb graphs are robust against function perturbations. In fact, it is clear that any data acquisition is subject to perturbations, noise and approximation errors and, if Reeb graphs were not stable, then distinct computational investigations of the same object could produce completely different results. In this paper we present an initial contribution to establishing stability properties for Reeb graphs. More precisely, focusing our attention on 1-dimensional manifolds, we define an editing distance between Reeb graphs, in terms of the cost necessary to transform one graph into another. Our main result is that changes in Morse functions imply smaller changes in the editing distance between Reeb graphs.

Stability of Reeb Graphs of Closed Curves / B., Di Fabio; Landi, Claudia. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - ELETTRONICO. - 283:(2012), pp. 71-76. [10.1016/j.entcs.2012.05.006]

Stability of Reeb Graphs of Closed Curves

LANDI, Claudia
2012

Abstract

Reeb graphs are very popular shape descriptors in computational frameworks as they capture both geometrical properties of the shape, and its topological features. Some different methodologies have been proposed in the literature to estimate the similarity of shapes through the comparison of the associated Reeb graphs. In this context, one of the most important open questions is whether Reeb graphs are robust against function perturbations. In fact, it is clear that any data acquisition is subject to perturbations, noise and approximation errors and, if Reeb graphs were not stable, then distinct computational investigations of the same object could produce completely different results. In this paper we present an initial contribution to establishing stability properties for Reeb graphs. More precisely, focusing our attention on 1-dimensional manifolds, we define an editing distance between Reeb graphs, in terms of the cost necessary to transform one graph into another. Our main result is that changes in Morse functions imply smaller changes in the editing distance between Reeb graphs.
2012
283
71
76
Stability of Reeb Graphs of Closed Curves / B., Di Fabio; Landi, Claudia. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - ELETTRONICO. - 283:(2012), pp. 71-76. [10.1016/j.entcs.2012.05.006]
B., Di Fabio; Landi, Claudia
File in questo prodotto:
File Dimensione Formato  
GETCODiFabio.pdf

Open access

Descrizione: Articolo principale
Tipologia: Versione pubblicata dall'editore
Dimensione 110.71 kB
Formato Adobe PDF
110.71 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/734448
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact