Metric Graph Reconstruction From Noisy Data

Mridul Aanjaneya 1 Frédéric Chazal 2 Daniel Chen 1 Marc Glisse 2 Leonidas J. Guibas 1 Dmitriy Morozov 3
1 Computer Science Department [Stanford]
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 LBNL - Lawrence Berkeley National Laboratory [Berkeley]
Abstract : Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs.19 Building on the notions of correspondence and Gromov-Hausdorff distance in metric geometry, we describe a model for such data sets as an approximation of an underlying metric graph. We present a novel algorithm that takes as an input such a data set, and outputs a metric graph that is homeomorphic to the underlying metric graph and has bounded distortion of distances. We also implement the algorithm, and evaluate its performance on a variety of real world data sets.
Keywords : topological data analysis metric graph resconstruction computational topology
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2012, 22 (4), pp.305-325. 〈10.1142/S0218195912600072〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01094867
Contributeur : Frédéric Chazal <>
Soumis le : dimanche 14 décembre 2014 - 10:54:24
Dernière modification le : mercredi 28 février 2018 - 17:00:44

Identifiants

Collections

INRIA

Citation

Mridul Aanjaneya, Frédéric Chazal, Daniel Chen, Marc Glisse, Leonidas J. Guibas, et al.. Metric Graph Reconstruction From Noisy Data. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2012, 22 (4), pp.305-325. 〈10.1142/S0218195912600072〉. 〈hal-01094867〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

188

Contact


archive-ouverte@inria.fr