Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure

Frédéric Chazal 1 Jian Sun 2
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 Mathematical Science Center
Tsinghua University [Beijing]
Abstract : 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.
Liste complète des métadonnées

https://hal.inria.fr/hal-00820599
Contributeur : Frédéric Chazal <>
Soumis le : lundi 6 mai 2013 - 11:02:36
Dernière modification le : jeudi 11 janvier 2018 - 16:21:44
Document(s) archivé(s) le : mardi 4 avril 2017 - 05:21:31

Fichiers

paper-metric-graph_v5.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00820599, version 1
  • ARXIV : 1305.1172

Collections

Citation

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

Partager

Métriques

Consultations de la notice

285

Téléchargements de fichiers

329