Fast Marching Method

[Lindley]

I'm trying to figure out the Fast Marching Method. Two things have become apparent:

1) I need a data structure which is a heap according to one key (arrival time), has an increase_key function, and is indexable by position as well. I have yet to find anything ideal, although I think I can approximate the behavior using an STL multiset without asymptotically worsening the runtime. It would require using equal_range to search on an existing key, and then walking through the possibilities to find the proper (x,y) entry to update. The actual update would need to be an erase/re-insert......why couldn't STL just give their heap algorithm an increase_key method?

2) I need to understand the update rule. I've been looking at:
http://sepwww.stanford.edu/public/docs/sep95/tariq5/paper_html/node3.html
But it's not clear to me how the two dimensions interact; and I can't make out the symbol under "delta s" in two of the key equations there, anyway. (Why not make the darn things big enough to read?)

[MikeAThon]

I can't help you with your first point, but for your second point, here is a pdf version of the paper you are relying on: http://sep.stanford.edu/oldsep/sergey/sepsergey/fmpolar.pdf

As you can see, the update equation uses delta-x (not delta-s) and the symbol under the delta-x is "v". Unfortunately, I searched the entire article, but the author does not say what "v" represents (the velocity maybe?)

Here is the original paper by Sethian and Popovici: http://citeseer.ist.psu.edu/cache/papers/cs/12299/http:zSzzSzwww.math.berkeley.eduzSz~sethianzSzPublicationszSz..zSzPaperszSzsethian.seismic.pdf/sethian98three.pdf . Maybe you will have better luck using the original.

Mike

[Lindley]

Actually, in a stroke of genius I asked my boss. Since he was one of the people who discovered the FMM at the same time as Sethian (independently), he was able to explain it very clearly. Doesn't get credit nearly as often as Sethian does, though.

As to the data structure, it occured to me that in most cases it's probably fine to just put duplicate entries in the heap, since the one we'll see first is the one we're interested in anyway.