Published 2011
| Version v1
Conference paper
Metric graph reconstruction from noisy data
Contributors
Others:
- Computer Science Department [Stanford] ; Stanford University
- Geometric computing (GEOMETRICA) ; Centre Inria d'Université Côte d'Azur (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre Inria de Saclay ; Institut National de Recherche en Informatique et en Automatique (Inria)
- Lawrence Berkeley National Laboratory [Berkeley] (LBNL)
- This work was supported in part by NSF grants CCF 0634803, FODAVA 0808515, CCF 1011228, a grant from Google Inc.
- European Project: 255827,EC:FP7:ICT,FP7-ICT-2009-C,CG LEARNING(2010)
Description
Many real-world data sets can be viewed of as noisy samples of special types of metric spaces called metric graphs. 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.
Abstract
International audienceAdditional details
Identifiers
- URL
- https://inria.hal.science/inria-00630774
- URN
- urn:oai:HAL:inria-00630774v1
Origin repository
- Origin repository
- UNICA