Metric Graph Reconstruction From Noisy Data

Mridul Aanjaneya; Frédéric Chazal; Daniel Chen; Marc Glisse; Leonidas J. Guibas; Dmitriy Morozov

Metric Graph Reconstruction From Noisy Data

Mridul Aanjaneya ¹ Frédéric Chazal ² Daniel Chen ¹ Marc Glisse ² Leonidas J. Guibas ¹ Dmitriy Morozov ³

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

Document type :

Journal articles

Domain :

Computer Science [cs] / Computational Geometry [cs.CG]

Complete list of metadatas

https://hal.inria.fr/hal-01094867
Contributor : Frédéric Chazal <>
Submitted on : Sunday, December 14, 2014 - 10:54:24 AM
Last modification on : Wednesday, February 28, 2018 - 5:00:44 PM

Metric Graph Reconstruction From Noisy Data

Identifiers

Collections

Citation

Export

Metrics

243

Contact

Metric Graph Reconstruction From Noisy Data

Identifiers

Collections

Citation

Export

Share

Metrics

243

Contact