Remarks on the O(N) Implementation of the Fast Marching Method
<|reference_start|>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, Bartesaghi and Sapiro have suggested to use 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 estimates implies in particular that the choice of an accuracy level that is independent of the speed function F results in the complexity bound O(Fmax /Fmin N). A numerical experiment illustrates this robustness problem for large ratios Fmax /Fmin .<|reference_end|>
@article{rasch2007remarks,
    title={Remarks on the O(N) Implementation of the Fast Marching Method},
    author={Christian Rasch and Thomas Satzger},
    journal={arXiv preprint arXiv:cs/0703082},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0703082},
    primaryClass={cs.NA}
}