Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure

Frédéric Chazal
Jian Sun
  • Fonction : Auteur
  • PersonId : 941015

Résumé

In many real-world applications data come as discrete metric spaces sampled around 1-dimensional filamentary structures that can be seen as metric graphs. In this paper we address the metric reconstruction problem of such filamentary structures from data sampled around them. We prove that they can be approximated, with respect to the Gromov-Hausdorff distance by well-chosen Reeb graphs (and some of their variants) and we provide an efficient and easy to implement algorithm to compute such approximations in almost linear time. We illustrate the performances of our algorithm on a few synthetic and real data sets.
Fichier principal
Vignette du fichier
paper-metric-graph_v5.pdf (3.19 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00820599 , version 1 (06-05-2013)

Identifiants

Citer

Frédéric Chazal, Jian Sun. Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure. 2013. ⟨hal-00820599⟩

Collections

INRIA INSMI INRIA2
245 Consultations
576 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More