Remarks on the O(N) implementation of the fast marching method

The fast marching algorithm computes an approximate solution to the eikonal equation in O(N log N) time, where the factor log N is due to the administration of a priority queue. Recently, Yatziv et al. ( 2006, J. Comput. Phys., 212, 393-399) have suggested using an untidy priority queue, reducing the overall complexity to O(N) at the price of a small error in the computed solution. In this paper we give an explicit estimate of the error introduced, which is based on a discrete comparison principle. This estimate implies, in particular, that the choice of an accuracy level that is independent of the speed function F results in the complexity bound being O(F(max)/F(min)N). A numerical experiment illustrates this robustness problem for large ratios F(max)/F(min).