The edit distance for Reeb graphs of surfaces

Di Fabio, Barbara ; Landi, Claudia (2014) The edit distance for Reeb graphs of surfaces. [Preprint]

This is the most updated version of the document.

Full text available as:
[thumbnail of RS140220.pdf]
Preview
PDF
License: Creative Commons: Attribution-Noncommercial 3.0 (CC BY-NC 3.0)

Download (232kB) | Preview
[thumbnail of RS141105_arXiv.pdf]
Preview
PDF
License: Creative Commons: Attribution-Noncommercial 3.0 (CC BY-NC 3.0)

Download (274kB) | Preview

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 metric 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 functions, measured by the maximum norm, imply not greater changes in the corresponding Reeb graphs, measured by the edit distance. The optimality result states that our edit distance discriminates Reeb graphs better than any other metric for Reeb graphs of surfaces satisfying the stability property.

Abstract
Document type
Preprint
Creators
CreatorsAffiliationORCID
Di Fabio, Barbara
Landi, Claudia
Keywords
shape similarity, graph edit distance, Morse function, natural stratification
Subjects
DOI
Deposit date
10 Nov 2014 08:27
Last modified
10 Nov 2014 08:27
URI

Other metadata

Available versions of this document

Downloads

Downloads

Staff only: View the document

^