Approximating the Riemannian Metric from Point Clouds via Manifold Moving Least Squares
This provides a theoretical foundation for improved geodesic distance approximations in computational geometry, with potential applications in fields like computer graphics and data analysis, though it is incremental as it builds on existing Manifold-MLS methods.
The paper tackles the problem of approximating geodesic distances and shortest paths on point clouds from embedded submanifolds, showing that the Riemannian metric of a Manifold-MLS approximating manifold converges to the original with a rate of O(h^{k-1}), and uses this to devise an algorithm with the same convergence rate.
The approximation of both geodesic distances and shortest paths on point cloud sampled from an embedded submanifold $\mathcal{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 $\mathcal{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 $\mathcal{M}\in C^{k}$ and closed (i.e. $\mathcal{M}$ is a compact manifold without boundary) the Riemannian metric of $ \mathcal{M}^h $ approximates the Riemannian metric of $ \mathcal{M}, $. Explicitly, given points $ p_1, p_2 \in \mathcal{M}$ with geodesic distance $ ρ_{\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 $ ρ_{\mathcal{M}^h}(p_1^h,p_2^h) = ρ_{\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.