Reading: Geodesic Distance and the Heat Method

For the final reading, we will take a look at the paper “The Heat Method for Distance Computation”, by Crane, Weischedel, and Wardetzky. Note that all students should do this reading, even if you’ve already completed four written/coding assignments. The hand-in instructions are the same as for all previous reading assignments; the reading is due on Thursday, December 14th.

4 thoughts on “Reading: Geodesic Distance and the Heat Method”

  1. the heat method is awesome! however, it seems that the output distance function is asymmetric: distance from $x$ to $y$ is slightly different from $y$ to $x$, since the heat kernel $k$ is in general asymmetric when $t>0$, i.e. $k_{t,x}(y) \ne k_{t,y}(x)$. Is there an elegant way to fix it other than a naïve (and brute force) symmetrization?

    1. That’s a great question, and it ties directly into the main theme of our course: what are all the properties of the distance function in the smooth setting? How can you preserve those properties in the discrete setting? And can you preserve all properties simultaneously?

      For instance, both the heat method and the fast marching method will produce a distance that doesn’t exactly satisfy the triangle inequality; the exact polyhedral distance will satisfy these properties, but produces the wrong “cut locus” (since every single vertex will be contained in the cut locus!). There is also some work on using strategies similar to the heat method to obtain a distance that exactly satisfies metric properties (symmetry and triangle inequality); see in particular Solomon et al, ”Earth Mover’s Distance on Discrete Surfaces.”

  2. I find the following weird: on top left of Page 94 of the journal (Communications of the ACM) or Page 5 of the file “HeatMethod.pdf”, the discrete equation reads $(M-tL_C)u=\delta_\gamma$. Shouldn’t it be $M\delta_\gamma$ on the right hand side as the volume/area element will pop up in the integration, just like the mass matrix on the left. Moreover, multiplying the mass matrix on the right is consistent with what we did for the mean curvature flow.

    1. Careful: a Dirac delta is, by definition, a distribution that integrates to 1. So when you integrate over dual cells you should get 1, independent of the size of the cell.

      Moreover, the divergence you compute for the next part is really the integral of divergence over the dual cell (discrete 2-form). So again you don’t need to explicitly include the mass matrix.

Leave a Reply