Geodesic In Heat For Pointcloud

Description of the geodesic in heat method applied on a point cloud.

Info! Unfinished notes

Propagation of heat

Let’s consider the propagation of the heat generated by a source located at the point $x$ over a point cloud. At the time $t$, the temperature at the point $y$ can be obtained using the heat kernel

$$k_{t,x}(y).$$

The Varadhan’s formula¹ states that the geodesic distance $\phi$ between any pair of points $x, y$ can be obtained by

$$\phi(x,y) = \lim_{t\rightarrow 0} \sqrt{-4t\log k_{t,x} (y)}.$$

Estimating the distance with this method can be inaccurate as it is hard to evaluate $k_{t,x} (y)$ and Crane et. al² proposed to use the gradient of the heat as a better approximation.

The heat method

The heat method is performed in three steps:

1. $X = - \nabla u~/~\vert\nabla u\vert$,
2. $\Delta \phi = \nabla \cdot X$.

The heat method on a point cloud

Estimation of the gradient with Weighted Least Squares from A. Nealen³.

References

1. S. R. S. Varadhan, On the behavior of the fundamental solution of the heat equation with variable coefficients, Communications on pure and applied mathematics, 1967. ↩

2. K. Crane and C. Weischedel, and M. Wardetzky, Geodesics in Heat:A New Approach to Computing Distance Based on Heat Flow, ACM, 2013. ↩

3. A. Nealen, An As-Short-As-Possible Introduction to the Least Squares, Weighted LeastSquares and Moving Least Squares Methods for Scattered DataApproximation and Interpolation, 2004 ↩