Application of Fibonacci heap to fast marching method

Abstract

The fast marching method (FMM) is an efficient, stable and adaptable travel time calculation method. In the realization of this method, it is necessary to select the minimum travel time node from the narrow band many times. The selection method has an important influence on the calculation efficiency of FMM. Traditional FMM adopts the binary tree heap sorting method to achieve this step. Fibonacci heap sort method to FMM will be applied in this study. Compared with the binary tree heap sorting method, the Fibonacci heap sort method can realize the minimum travel time node selection in the narrow band in a more efficient way when the number of the narrow-band nodes is huge. The new method will be verified through error analysis and two numerical model calculations.

Keywords

• fast marching method
• fibonacci heap sort
• travel time calculation
• seismic wave propagation
• eikonal equation