Geodesics in heat: A new approach to computing distance based on heat flow

We introduce the heat method \nfor computing the geodesic distance to a \nspecified subset (e.g., point or curve) of a given domain. The heat method is robust, efficient, and simple to implement since it is based on solving \na pair of standard linear elliptic problems. The resulting systems can be prefactored once and subsequently solved in near-linear time. In practice, \ndistance is updated an order of magnitude faster than with state-of-the-art \nmethods, while maintaining a comparable level of accuracy. The method requires only standard differential operators and can hence be applied on \na wide variety of domains (grids, triangle meshes, point clouds, etc.). We \nprovide numerical evidence that the method converges to the exact distance \nin the limit of refinement; we also explore smoothed approximations of \ndistance suitable for applications where greater regularity is required.