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 ^2) approximations at most . 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 M^h using information from a given point cloud that was developed by Sober \& Levin in 2019 . They showed that the Manifold-MLS procedure approximates the original manifold with approximation order of O(h^{k M\in C^{k} is closed , i.e. M is a compact manifold without boundary . In this paper, we show that under the same conditions, the Riemannian metric of M^h approximates the Riemannian metric of M, ; i. e., \mathcal{M Explicitly, given points p_1, p_2 \in \mathcal{M} with geodesic distance \rho_{\mathcal{M}}(p_1, p_2) , we show that their corresponding points p_1^h, p_2^h \in \mathcal{M}^h have a geodesic distance of \rho_{\mathcal{M}^h}(p_1^h,p_2^h) = \rho_{\mathcal{M}}(p_1, p_2)  + O(h^{k-1}) . We then use this result, as well as the fact that \mathcal{M}^h can be sampled with any desired resolution, to devise a naive algorithm that yields approximate geodesic distances with  rate of convergence O(h^{k-1}) . We show the potential and the robustness to noise of the proposed method on some numerical simulations.
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 M^h using information from a given point cloud that was developed by Sober \& Levin in 2019. In this paper, we show that provided that M\in C^{k} and closed ( i.e. M is a compact manifold without boundary ) the Riemannian metric of M^h approximates the Riemannian metric of M, . Explicitly, given points p_1, p_2 \in \mathcal{M} with geodesic distance \rho_{\mathcal{M}}(p_1, p_2) , we show that their corresponding points p_1^h, p_2^h \in \mathcal{M}^h have a geodesic distance of \rho_{\mathcal{M}^h}(p_1^h,p_2^h) = \rho_{\mathcal{M}}(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 \mathcal{M}^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.
R
^2) approximations at most
) provable approximations
R
2019 . They showed that the Manifold-MLS procedure approximates the original manifold with approximation order of O(h^{k
2019. In this paper, we show that provided that
R
is closed ,
and closed (
R
. In this paper, we show that under the same conditions, the
) the
R
; i. e., \mathcal{M
.
A
(1
R
.
) (i.e., the Manifold-MLS is nearly an isometry).
A
a