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

Abstract

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
Pages37-46
Number of pages10
ISBN (Print)9781450306829
DOIs
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

Keywords

  • Inference
  • Metric graph
  • Noise
  • Reconstruction

Fingerprint

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

Cite this