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

By Keenan Crane, Clarisse Weischedel, Max Wardetzky. TOGS, 2012

573 citations recorded by the source corpus.

We introduce the heat method for computing the geodesic distance to a specified 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 a pair of standard linear elliptic problems. The resulting systems can be prefactored once and subsequently solved in near-linear time. In practice, distance is updated an order of magnitude faster than with state-of-the-art methods, while maintaining a comparable level of accuracy. The method requires only standard differential operators and can hence be applied on a wide variety of domains (grids, triangle meshes, point clouds, etc.). We provide numerical evidence that the method converges to the exact distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where greater regularity is required.

Subfields: Computational Mechanics, Management, Monitoring, Policy and Law

View Paper: https://www.semanticscholar.org/paper/910c352ab7ccd919ba301548e7c5f87fc74762d8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Management, Monitoring, Policy and Law

Citations in the corpus

Multi-Garment Net: Learning to Dress 3D People From Images (2019, methodology): “t-shirts of different sleeve lengths), we define a cost increasing with the geodesic distance distgeo(v) : S 7→ R from the garment region boundary – efficiently computed based on heat flow [15].”
Bayesian Inference of Bijective Non-Rigid Shape Correspondence (2016, background): “For example, diffusion distances [14] or other approximations of the geodesic distances [15] are likely to work equally well while being better amenable both for faster computation and more compact storage.”
Entropic Approximation of Wasserstein Gradient Flows (2015, methodology): “Inspired by the “geodesic in heat” method of [31], it has recently been proposed by [67] to speed up these computations by approximating the kernel ξ by a Laplace or a heat kernel ξ̃ (depending on whether α = 1 or α = 2).”
Computational Optimal Transport (2018, methodology): “The use of Varadhan’s formula to approximate geodesic distances was initially proposed in [Crane et al., 2013] and its use in conjunction with Sinkhorn iterations in [Solomon et al.”
NASA: Neural Articulated Shape Approximation (2019, background): “Further, this approximation can be explained via the algebraic relationship between heat kernels and distance functions [11].”