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 ℳ 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 ℳ^h using information from a given point cloud that was developed by Sober & Levin in 2019. In this paper, we show that provided that ℳ∈ C^k and closed (i.e. ℳ is a compact manifold without boundary) the Riemannian metric of ℳ^h approximates the Riemannian metric of ℳ,. Explicitly, given points p_1, p_2 ∈ℳ with geodesic distance ρ_ℳ(p_1, p_2), we show that their corresponding points p_1^h, p_2^h ∈ℳ^h have a geodesic distance of ρ_ℳ^h(p_1^h,p_2^h) = ρ_ℳ(p_1, p_2)(1 + O(h^k-1)) (i.e., the Manifold-MLS is nearly an isometry). We then use this result, as well as the fact that ℳ^h can be sampled with any desired resolution, to devise a naive algorithm that yields approximate geodesic distances with a rate of convergence O(h^k-1). We show the potential and the robustness to noise of the proposed method on some numerical simulations.
READ FULL TEXT