## Ordered Upwind Methods

In [101,129], Sethian and Vladimirsky developed a novel extension of the fast marching method, making it applicable to a significantly wider class of problems.

Recall the fast marching method equation

It is important to recognize that this equation assumes that from any point x, the speed, F, is the same, independent of the direction the interface is traveling. In other words, the speed function is isotropic. Sethian and Vladimirsky have generalized the fast marching method so that the speed function can vary with direction, i.e. the speed function, F, may depend on V0. In this case, the speed function is called anisotropic. The generalized method is called the ordered upwind method, of which the fast marching method is a special case.

Figure 4.11: Illustration of the difficulty with anisotropic speed functions. Which path is optimal depends on the speed and direction.

To illustrate the difference, consider the problem of finding the fastest route between two cities. If the problem were isotropic, then it would mean that you will travel at the same speed regardless of the direction you are traveling. The solution is therefore simple: a straight line pathbetween the two cities. However, in reality, there are roads, bridges, rivers, mountains, and other assorted terrain features that can influence the choice of the path. When on a road, the speed function depends heavily on the direction to be traveled, with the highest speed along the road and the slowest speed off the road.

The example of the road highlights one of the key technical issues that had to be addressed in this paper. In the isotropic case, when computing an estimate for the value of 0(x), it is sufficient to only check immediately neighboring points. In the anisotropic case, this is not the case. When standing at a point on the road, one must check not only the immediate neighborhood, but must also check far down the road to see if a shorter path along the road would be possible. This comparison is illustrated in Fig. 4.11, where the shortest path arriving at point B may not be directly from nearby points, but may come from far away points along directions which are faster. The key observation in [129] was the identification of how far away one must check to assure locating the shortest path.

More specifically, the ordered upwind method solves equations of the form

with the additional assumption that F(V0, x) > 0 is convex. The case where F is non-convex is significantly more challenging and remains an open problem.

The algorithm for the ordered upwind method is similar to the fast marching method described in Section 4.2.3, with only step 3 requiring modification. In the fast marching method, when a point x is moved from the tentative set, T, to the accepted set, A, only the immediately adjacent grid points require the approximate value of 4 to be updated. Let Fmin and Fmax be the minimum and maximum values of the speed function F. For the more general ordered upwind method, all the tentative points in a radius of AxFmax/Fmin around x must be updated. If the new approximate value for 4 is smaller, this new value is used. This is to account for the possible highest speed direction which could allow the point x to influence grid points within this radius before the immediately adjacent grid points. The formulation for computing the approximation for 4 at these tentative points uses the same type of one-sided discretization as used in the fast marching method to follow the characteristics from x.

As an example of the use of the ordered upwind method, the geodesic distance from the origin on the manifold 2 = 4 sin(3^x) sin(3^y) is computed on the square [—1, 1] x [ — 1, i]inthex-yplane. The resulting distance isocontours are shown in Fig. 4.12