Paper Info
Title
Geodesics in heat: A new approach to computing distance based on heat flow
Abstract
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.
Year
DOI
Venue
2013
10.1145/2516971.2516977
ACM Trans. Graph.
Keywords
DocType
Volume
state-of-the-art method,comparable level,standard differential operator,geodesic distance,point cloud,exact distance,method converges,heat method,greater regularity,new approach,heat flow,standard linear elliptic problem,computing distance
Journal
32
Issue
ISSN
Citations 
5
ACM Trans. Graph. 32 (5), 2013
47
PageRank 
References 
Authors
1.08
15
3
Name
Order
Citations
PageRank
Keenan Crane158629.28
Clarisse Weischedel2681.73
Max Wardetzky347521.63