Reeb graphs are structural descriptors that capture shape properties of a topological space from the perspective of a chosen function. In this work, we define a combinatorial distance for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions of this paper are the stability property and the optimality of this edit distance. More precisely, the stability result states that changes in the Reeb graphs, measured by the edit distance, are as small as changes in the functions, measured by the maximum norm. The optimality result states that the edit distance discriminates Reeb graphs better than any other distance for Reeb graphs of surfaces satisfying the stability property.

The Edit Distance for Reeb Graphs of Surfaces / DI FABIO, Barbara; Landi, Claudia. - In: DISCRETE & COMPUTATIONAL GEOMETRY. - ISSN 0179-5376. - STAMPA. - 55:2(2016), pp. 423-461. [10.1007/s00454-016-9758-6]

The Edit Distance for Reeb Graphs of Surfaces

DI FABIO, Barbara;LANDI, Claudia
2016

Abstract

Reeb graphs are structural descriptors that capture shape properties of a topological space from the perspective of a chosen function. In this work, we define a combinatorial distance for Reeb graphs of orientable surfaces in terms of the cost necessary to transform one graph into another by edit operations. The main contributions of this paper are the stability property and the optimality of this edit distance. More precisely, the stability result states that changes in the Reeb graphs, measured by the edit distance, are as small as changes in the functions, measured by the maximum norm. The optimality result states that the edit distance discriminates Reeb graphs better than any other distance for Reeb graphs of surfaces satisfying the stability property.
55
2
423
461
The Edit Distance for Reeb Graphs of Surfaces / DI FABIO, Barbara; Landi, Claudia. - In: DISCRETE & COMPUTATIONAL GEOMETRY. - ISSN 0179-5376. - STAMPA. - 55:2(2016), pp. 423-461. [10.1007/s00454-016-9758-6]
DI FABIO, Barbara; Landi, Claudia
File in questo prodotto:
File Dimensione Formato  
DCG_Reeb_surfaces.pdf

non disponibili

Descrizione: Articolo principale
Tipologia: Versione dell'editore (versione pubblicata)
Dimensione 1.69 MB
Formato Adobe PDF
1.69 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
POST PRINT_THE EDIT DISTANCE FOR REEB GRAPHS OF SURFACES.pdf

accesso aperto

Tipologia: Post-print dell'autore (bozza post referaggio)
Dimensione 268.36 kB
Formato Adobe PDF
268.36 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento 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/1084788
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 9
social impact