# A better Fast Marching Method?

I am using the Fast Marching Method (FMM) to calculate shortest "distance" (traveltime) from some points.

The way FMM works is: I keep a velocity function in RAM: V(xi,yj,zk). I also keep a priority queue of all points on the front sorted on their V value. I repeatedly propagate the first point in this queue one step outwards. As I do this I remove the used point from the queue and insert those "touched" by the front.

My current implementation have two problems:

I. I must keep the whole cost (slowness) function in RAM. This limits the size of the cost function I can use.

II. I would like it to be even faster.

Any suggestions on how to improve my current implementation? For instance would it be possible to implement this on the GPU?

• Could you give us more information? We can't really suggest improvements to your implementation without knowing which library you got it from, or how you implemented it yourself. – Godric Seer Jan 23 '13 at 13:42
• I am the OP. I added a bit extra info (it is being peer-reviewed). – Andy Jan 24 '13 at 8:58
• @Andy This answer about parallelization (for the Eikonal equation) has some information about fast sweeping Eikonal solvers and their limitations. Now that I know that the OP is still around, I might even decide to write a more detailed answer (if nobody else does it). – Thomas Klimpel Jan 24 '13 at 15:42

The observation behind the fast sweeping methods is that for the updates it is only important in which of $2^n$ "general directions" the characteristics point. Especially any region where this "general direction" is constant can be updated by a sweep. Still, there are many different ways to turn this observation into an algorithm, and which strategy will be most efficient depends a bit on whether your velocity function leads to large regions with constant "general direction", or whether it creates more a sort of labyrinth.