Metric graph reconstruction from noisy data

Mridul Aanjaneya, Frederic Chazal, Daniel Chen, Marc Glisse, Leonidas Guibas, Dmitriy Morozov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations


Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs [16]. 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 the underlying metric graph with guarantees. We also implement the algorithm, and evaluate its performance on a variety of real world data sets.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th Annual Symposium on Computational Geometry, SCG'11
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)9781450306829
StatePublished - 2011
Externally publishedYes

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


  • Inference
  • Metric graph
  • Noise
  • Reconstruction


Dive into the research topics of 'Metric graph reconstruction from noisy data'. Together they form a unique fingerprint.

Cite this