The Heat Method for Distance Computation
The Heat Method for Distance Computation
复制标题
DOI：
10.1145/3131280
复制
发表时间：
2017-11-01
影响因子：
22.7
通讯作者：
Wardetzky, Max
中科院分区：
文献类型：
--
作者：
Crane, Keenan;Weischedel, Clarisse;Wardetzky, Max
介绍了求解平面和曲面上单源或多源最短路问题的热方法。一个关键的见解是，距离计算可以分为两个阶段：首先找到距离增加的方向沿着，然后计算距离本身。热方法是鲁棒的，高效的，简单的实现，因为它是基于解决一对标准的稀疏线性系统。这些系统可以分解一次，随后在接近线性的时间内解决，大大降低了摊销成本。真实世界的性能比最先进的方法快一个数量级，同时保持相当的准确度。该方法可以应用于任何维度，并在任何领域，承认梯度和内积-包括规则网格，三角形网格，和点云。数值证据表明，该方法收敛到精确的距离在限制的细化，我们还探讨了平滑的近似距离适合的应用程序，需要更大的规律性。
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.