“Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow” by Crane, Weischedel and Wardetzky
Conference:
Type(s):
Title:
- Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow
Session/Category Title: Surfaces & Differential Geometry
Presenter(s)/Author(s):
Moderator(s):
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.
References:
- Alexa, M. and Wardetzky, M. 2011. Discrete laplacians on general polygonal meshes. ACM Trans. Graph. 30, 4, 102:1–102:10.
- Belkin, M., Sun, J., and Wang, Y. 2009a. Constructing laplace operator from point clouds in Rd. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA’09).
- Belkin, M., Sun, J., and Wang, Y. 2009b. Discrete laplace operator for meshed surfaces. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms (SODA’09). 1031–1040.
- Bommes, D. and Kobbelt, L. 2007. Accurate computation of geodesic distance fields for polygonal curves on triangle meshes. In Proceedings of the Workshop on Vision, Modeling, and Visualization (VMV’07). 151–160.
- Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In Proceedings of the IMA Conference on the Mathematics of Surfaces. Springer, 62–83.
- Campen, M. and Kobbelt, L. 2011. Walking on broken mesh: Defect-tolerant geodesic distances and parameterizations. Comput. Graph. Forum 30, 2, 623–632.
- Chebotarev, P. 2011. The walk distances in graphs. ArXiv e-prints.
- Chen, Y., Davis, T. A., Hager, W. W., and Rajamanickam, S. 2008. Algorithm 887: CHOLMOD, supernodal sparse cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 3.
- Coifman, R. R. and Lafon, S. 2006. Diffusion maps. Appl. Comput. Harmon. Anal. 21, 5–30.
- Desbrun, M., Kanso, E., and Tong, Y. 2008. Discrete differential forms for computational modeling. In Discrete Differential Geometry. Oberwolfach Seminars, vol. 38. Birkhauser, 287–324.
- Fouss, F., Pirotte, A., Renders, J.-M., and Saerens, M. 2007. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans. Knowl. Data Engin. 19, 3, 355–369.
- Hildebrandt, K. and Polthier, K. 2011. On approximation of the laplace-beltrami operator and the willmore energy of surfaces. Comput. Graph. Forum 30, 5, 1513–1520.
- Hysing, S. and Turek, S. 2005. The eikonal equation: Numerical efficiency vs. algorithmic complexity. In Proceedings of the Algoritmy Conference. 22–31.
- Jiang, G. and Peng, D. 1997. Weighted eno schemes for hamilton-jacobi equations. SIAM J. Sci. Comput. 21, 2126–2143.
- Kimmel, R. and Sethian, J. A. 1998. Fast marching methods on triangulated domains. Proc. Nat. Acad. Sci. 95, 8341–8435.
- Lipman, Y., Rustamov, R. M., and Funkhouser, T. A. 2010. Biharmonic distance. ACM Trans. Graph. 29, 3.
- Liu, Y., Prabhakaran, B., and Guo, X. 2012. Point-based manifold harmonics. IEEE Trans. Vis. Comput. Graph. 18, 10, 1693–1703.
- Luo, C., Safa, I., and Wang, Y. 2009. Approximating gradients for meshes and point clouds via diffusion metric. Comput. Graph. Forum 28, 5, 1497–1508.
- Macneal, R. 1949. The solution of partial differential equations by means of electrical networks. Ph.D. dissertation, Caltech.
- Memoli, F. and Sapiro, G. 2001. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces. J. Comput. Phys. 173, 730–764.
- Memoli, F. and Sapiro, G. 2005. Distance functions and geodesics on submanifolds of ℝd and point clouds. SIAM J. Appl. Math. 65, 4.
- Mitchell, J., Mount, D., and Papadimitriou, C. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4, 647–668.
- Nealen, A. 2004. An as-short-as-possible introduction to the mls method for scattered data approximation and interpolation. Tech. rep. http://www.nealen.net/projects/mls/asapmls.pdf.
- Neel, R. and Stroock, D. 2004. Analysis of the cut locus via the heat kernel. Surv. Differen. Geom. 9, 337–349.
- Norris, J. 1997. Heat kernel asymptotics and the distance function in lipschitz Riemannian manifolds. Acta Math. 179, 1, 79–103.
- Peyre, G. and Cohen, L. D. 2005. Geodesic computations for fast and accurate surface remeshing and parameterization. In Programs in Nonlinear Differential Equations and Their Applications. Vol. 63. Springer, 157–171.
- Rangarajan, A. and Gurumoorthy, K. 2011. A fast eikonal equation solver using the schrodinger wave equation. Tech. rep. REP-2011-512, CISE, University of Florida.
- Rustamov, R., Lipman, Y., and Funkhouser, T. 2009. Interior distance using barycentric coordinates. Comput. Graph. Foru, 28, 5.
- Schmitz, P. G. and Ying, L. 2012. A fast direct solver for elliptic problems on general meshes in 2d. J. Comput. Phys. 231, 4.
- Schwarz, G. 1995. Hodge Decomposition: A Method for Solving Boundary Value Problems. Springer.
- Sethian, J. A. 1996. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision and Materials Science. Cambridge University Press.
- Spielman, D. A. and Teng, S.-H. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the ACM Symposium on Theory of Computation (STOC’04). ACM Press, New York, 81–90.
- Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3, 553–560.
- Varadhan, S. R. S. 1967. On the behavior of the fundamental solution of the heat equation with variable coefficients. Comm. Pure Appl. Math. 20, 2, 431–455.
- Villa, E. 2006. Methods of geometric measure theory in stochastic geometry. Ph.D. dissertation, Universita degli Studi di Milano.
- Von Renesse, M.-K. 2004. Heat kernel comparison on alexandrov spaces with curvature bounded below. Potent. Anal. 21, 2.
- Weber, O., Devir, Y. S., Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2008. Parallel algorithms for approximation of distance maps on parametric surfaces. ACM Trans. Graph. 27, 4.