Name
Abstract | ||
|---|---|---|
We introduce the heat method for computing the shortest 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 method represents a significant breakthrough in the practical computation of distance on a wide variety of geometric domains, since the resulting linear systems can be prefactored once and subsequently solved in near-linear time. In practice, distance can be updated via the heat method an order of magnitude faster than with state-of-the-art methods while maintaining a comparable level of accuracy. We provide numerical evidence that the method converges to the exact geodesic distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where more regularity is required. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2516971.2516977 | CoRR |
Keywords | DocType | Volume |
Algorithms,Digital geometry processing,discrete differential geometry,geodesic distance,distance transform,heat kernel | Journal | abs/1204.6216 |
Issue | ISSN | Citations |
5 | ACM Trans. Graph. 32 (5), 2013 | 21 |
PageRank | References | Authors |
0.64 | 11 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keenan Crane | 1 | 586 | 29.28 |
| Clarisse Weischedel | 2 | 68 | 1.73 |
| Max Wardetzky | 3 | 475 | 21.63 |