Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure
This addresses the metric reconstruction problem for data sampled around 1-dimensional structures, which is incremental as it builds on existing methods like Reeb graphs for specific applications.
The paper tackles the problem of reconstructing filamentary structures from discrete metric data by proving they can be approximated using Reeb graphs with respect to the Gromov-Hausdorff distance, and it provides an efficient algorithm that runs in almost linear time.
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.