Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure

In many real-world applications data come as discrete metric spaces sampled around 1-dimensional filamentary structures that can be seen as metric graphs. In this paper we address the metric reconstruction problem of such filamentary structures from data sampled around them. We prove that they can be approximated, with respect to the Gromov-Hausdorff distance by well-chosen Reeb graphs (and some of their variants) and we provide an efficient and easy to implement algorithm to compute such approximations in almost linear time. We illustrate the performances of our algorithm on a few synthetic and real data sets.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00820599
Author Chazal, Frédéric, Sun, Jian
Maintainer CCSD
Last Updated May 11, 2026, 05:18 (UTC)
Created May 11, 2026, 05:18 (UTC)
Identifier hal-00820599
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Geometric computing (GEOMETRICA) ; Centre Inria d'Université Côte d'Azur ; 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)
creator Chazal, Frédéric
date 2013-05-01T00:00:00
harvest_object_id 188c6bcb-e52c-428e-ae96-5e1167dbef5b
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-03-11T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1305.1172
set_spec type:UNDEFINED