Gromov-Hausdorff Approximation of Filament Structure Using Reeb-type Graph

In many real-world applications data appear to be sampled around1-dimensional filamentary structures that can be seen as topologicalmetric graphs. In this paper we address the metric reconstructionproblem of such filamentary structures from data sampled aroundthem. We prove that they can be approximated, with respect tothe Gromov-Hausdorff distance by well-chosen Reeb graphs (andsome of their variants) and we provide an efficient and easy to implementalgorithm to compute such approximations in almost lineartime. We illustrate the performances of our algorithm on a few datasets.