The heat method for distance computation
Citations Over TimeTop 1% of 2017 papers
Abstract
We introduce the heat method for solving the single- or multiple-source shortest path problem on both flat and curved domains. A key insight is that distance computation can be split into two stages: first find the direction along which distance is increasing, then compute the distance itself. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard sparse linear systems. These systems can be factored once and subsequently solved in near-linear time, substantially reducing amortized cost. Real-world performance is an order of magnitude faster than state-of-the-art methods, while maintaining a comparable level of accuracy. The method can be applied in any dimension, and on any domain that admits a gradient and inner product---including regular grids, triangle meshes, and point clouds. Numerical evidence indicates 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 desired.
Related Papers
- → A Gluing Method for Non-matching Meshes(2013)1 cited
- → Decomposing Scanned Assembly Meshes Based on Periodicity Recognition and Its Application to Kinematic Simulation Modeling(2010)
- → A Technique for the Long Term Preservation of Finite Element Meshes(2014)
- Wavelet-Based Multi-Resolution Analysis of Irregular Meshes(2007)
- → EFFECTIVE POROSITY OF 3D PRINTED SURGICAL MESHES(2023)