Wave propagation time optimization for geodesic distances calculation using the Heat Method

Abstract

Finding the geodesic path defined as the shortest paths between two points on three-dimensional surface P is a well known problem in differential and computational geometry. Surfaces are not differentiable in a discrete way, hence known geometry algorithms can’t be used directly - they have to be discretized first. Classic algorithms for geodesic distance calculation such as Mitchell-Mount-Papadimitriou method (MMP) are precise but slow. Therefore modern solutions are developed for fast calculations. One of them is Heat Method which approximates such paths with some accuracy. In this paper we propose the extension of Heat Method to reduce the approximation error. A new formula for calculating value of the parameter t (wave propagation time step) which outperforms the original one in terms of mean and median error is presented. Also, correlation between mesh properties and best wave propagation time step as well as influence of variable node spacing on heat map based method were thoroughly analysed.

Keywords

• geodesic distances
• heat method
• three-dimensional meshes
• mmp
• 02.40.-k
• 07.05.tp
• 07.05.wr
• 07.05.-t