Remarks on the O(N) Implementation of the Fast Marching Method

Details Remarks on the O(N) Implementation of the Fast Marching Method Remarks on the O(N) Implementation of the Fast Marching Method

2007-03-15

arxiv.org/abs/cs/0703082v1

Computer Science

Numerical Analysis

7 pages, 2 figures

Scientific paper

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 .

Affiliated with

Also associated with

No associations

Rating

Remarks on the O(N) Implementation of the Fast Marching Method does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Remarks on the O(N) Implementation of the Fast Marching Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Remarks on the O(N) Implementation of the Fast Marching Method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-363622