Name
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.
|
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3131280 | Communications of the ACM |
Field | DocType | Volume |
Mathematical optimization,Polygon mesh,Linear system,Shortest path problem,Computer science,Approximations of π,Algorithm,Theoretical computer science,Point cloud,Order of magnitude,Computation | Journal | 60 |
Issue | ISSN | Citations |
11 | 0001-0782 | 6 |
PageRank | References | Authors |
0.52 | 20 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keenan Crane | 1 | 586 | 29.28 |
| Clarisse Weischedel | 2 | 6 | 0.52 |
| Max Wardetzky | 3 | 475 | 21.63 |