---
abstract: 'The approximation of both geodesic distances and shortest paths on point cloud sampled from an embedded submanifold $\MM$ 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. 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 . They showed that the Manifold-MLS procedure approximates the original manifold with approximation order of $ O(h^{k})$ provided that the original manifold $\MM \in C^{k}$ is closed, i.e. $\MM$ is a compact manifold without boundary. In this paper, we show that under the same conditions, the Riemannian metric of $ \Mh $ approximates the Riemannian metric of $ \MM, $; i.e., $\MM$ is nearly isometric to $\Mh$. Explicitly, given points $ p_1, p_2 \in \MM $ with geodesic distance $ \rho_\MM(p_1, p_2) $, we show that their corresponding points $ p_1^h, p_2^h \in \Mh $ have a geodesic distance of $ \rho_\Mh(p_1^h,p_2^h) = \rho_\MM(p_1, p_2) + O(h^{k-1}) $. 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 rate of convergence $ O(h^{k-1}) $. We show the potential and the robustness to noise of the proposed method on some numerical simulations.'
author:
- Barak Sober
- Ingrid Daubechies
- Robert Ravier
bibliography:
- 'GeodesicsApprox.bib'
title: Approximating the Riemannian Metric from Point Clouds via Manifold Moving Least Squares
---

Introduction
============

The concept of a manifold is fundamental to models in numerous research fields (e.g., mathematical physics, linear algebra, computer graphics, computer aided design). In recent years, manifold-based modeling has also permeated into general high dimensional data analysis as a method of circumventing the curse of dimensionality (e.g., signal processing, computer vision, biomedical imaging). These “*data-driven*" models, however, do not follow from a set of equations or some other formal representation, but rather emerge from a general intuition/observation that data has low intrinsic dimensions, at least locally (see, for example, [@belkin2003laplacian; @coifman2006diffusion; @roweis2000LLE; @saul2003think; @tenenbaum2000global]). The lack of formalism means that both explicit coordinate charts and Riemannian metric structure are usually not available; in practice, the only information available is the collection of samples, i.e., *point clouds*.

An essential tool for data analysis in modern data-driven scenarios is the ability to measure intrinsic geodesic distances. The approximation of geodesic distances and geodesic paths on point clouds and their manifolds has been studied extensively in computer graphics literature, primarily in the context of 3D point clouds that represent 2D surfaces. The focus of these studies is on performing efficient approximations of high approximation order (for example, [@mitchell1987discrete; @sethian1996fast; @kimmel1998computing]). In most of these methods there is a strong assumption that a meshing of the manifold exists, which is a nontrivial requirement for general point clouds. To the best of our knowledge, the highest order of convergence proven in the literature is $ O(h) $ (for a resolution parameter $ h $) shown in the Fast Marching Method of Kimmel and Sethian [@kimmel1998computing]. Numerically, the work in [@lichtenstein2019deep] reports $ O(h^2) $ convergence rates in numerical simulations. Nonetheless, much less attention have been given to the general manifold case, where a triangulation cannot be achieved easily. Memoli and Sapiro [@memoli2005distance] proposed an approach for general submanifold of $ \RR^D $ with convergence rates of $ O(\sqrt{h}) $.

Many works deal with the lack of triangulation by instead using standard shortest path algorithms, such as the well-known Dijkstra algorithm [@dijkstra1959note], after imposing a graph structure on the point cloud based on distance information. Though nonexhaustive, see, for example, [@moscovich2016minimax; @tenenbaum2000global; @lin2008riemannian; @ravier2018algorithms; @ravier2018eyes]. However, approximating geodesic curves and distances from discrete samples in such a way may result in poor approximations if the sampling resolution is insufficient. Figure \[fig:DiscreteShortestPath\_Problem\]. gives an example of such a failure. As discussed in Section \[sec:Numerical\], in such cases, it is possible (though by no means guaranteed) that the Euclidean distance between points on the manifold serve as a better approximation to the geodesic distance.

![Shortest path from discrete samples of a 2-sphere. (A) The original manifold $ \MM $; the shortest path computed between $ p_1, p_2 $ (marked by red triangles) on discrete samples of the manifold (the path marked by the red line). (B) The sample set of $ \MM $ and the shortest path connecting points $ p_1, p_2 $ marked by the red triangles.[]{data-label="fig:DiscreteShortestPath_Problem"}](shortest_path.png){width="\linewidth"}

The main contribution of the current work is theoretical. In [@sober2019manifold], Sober and Levin proposed a procedure called Manifold Moving Least Squares (Manifold-MLS) that defined an implicit manifold from a given point cloud. Explicitly, given a Point Cloud sampled from a manifold $ \MM\in \C^k $ ($ k\geq 2 $) with sampling resolution $ h $ (such as the fill distance; see below), they introduce a moving least squares (MLS) procedure to create an approximating manifold $ \Mh.$ They show that $\PP:\MM\to\Mh$, the Manifold-MLS mapping from $\MM$ to $\Mh$, is a diffeomorphism. Similar to standard MLS approximations, the approximating manifold exists as an abstract object and can be realized at a point based upon a local neighborhood, requiring no global processing. Sober and Levin also show that the Hausdorff distance between $ \Mh $ and $ \MM $ is bounded by $ O(h^k) $.

In this paper, we show that the Riemannian metric of $ \Mh $ approximates the Riemannian metric of $ \MM $ as well. Specifically, let $ p_1, p_2 \in \MM $ with geodesic distance $ \rho_{\MM}(p_1, p_2) $ then $$\rho_{\Mh}(p^h_1, p^h_2) = \rho_{\MM}(p_1, p_2) + O(h^{k-1})
,$$ where $ p^h_1, p^h_2\in \Mh $ are $ O(h^k) $ away from $ p_1, p_2,$ respectively, and $ \rho_{\Mh}(p^h_1, p^h_2) $ is the Riemannian distance between $ p^h_1, p^h_2 $ on $ \Mh $ (see Theorem \[thm:MainResult\]). We prove this by showing that $\PP$ is actually an approximate isometry given that $\MM$ is sampled densely enough. In other words, the differential of $\PP$ is close to the identity map. In Section \[sec:Numerical\], we show how this result can be utilized by developing a simple brute-force algorithm that significantly improves the estimation of geodesics and their distances. The proposed algorithm can be shown to converge with a rate of $ O(h^{k-1}),$ a significant improvement on other results. We provide experimental evidence showing the potential of using the Manifold-MLS as well as its robustness to noise. We believe that the current work will motivate the future development of novel, efficient ways of approximating geodesics on point clouds

Definitions, Assumptions and the Approximation {#sec:Preliminaries}
==============================================

Proof of Theorem \[thm:MainResult\] {#sec:proof}
===================================

Numerical Simulations {#sec:Numerical}
=====================

Acknowledgments {#acknowledgments .unnumbered}
===============

Sets, Quasi Uniform Sampling and Interior Cone Condition {#sec:Appendix}
========================================================
