Approximating the Riemannian Metric from Point Clouds via Manifold Moving Least Squares

The approximation of both geodesic distances and shortest paths on point cloud sampled from an embedded submanifold M of Euclidean space has been a long-standing challenge in computational geometry. Given a sampling resolution parameter h , state-of-the-art discrete methods yield O(h) provable approximations. In this paper, we investigate the convergence of such approximations made by Manifold Moving Least-Squares (Manifold-MLS), a method that constructs an approximating manifold Mh using information from a given point cloud that was developed by Sober & Levin in 2019. In this paper, we show that provided that M∈ Ck and closed (i.e. M is a compact manifold without boundary) the Riemannian metric of Mh approximates the Riemannian metric of M, . Explicitly, given points p1, p2 ∈ M with geodesic distance ρM(p1, p2) , we show that their corresponding points p1h, p2h ∈ Mh have a geodesic distance of ρMh(p1h,p2h) = ρM(p1, p2)(1 + O(hk-1)) (i.e., the Manifold-MLS is nearly an isometry). We then use this result, as well as the fact that Mh can be sampled with any desired resolution, to devise a naive algorithm that yields approximate geodesic distances with a rate of convergence O(hk-1) . We show the potential and the robustness to noise of the proposed method on some numerical simulations.