13.5 Finite Difference Schemes

The level set equation

can be viewed as a special Hamilton-Jacobi equation

In order to discretize the level set equation (13.2), one approach is to substitute the time derivative with a forward difference and the spatial derivatives with central differences. Considering the case of a corner with a right angle at the outside (for the shape cf. Figure 13.5) and a constant speed function shows that the central difference approximation chooses a wrong value for the gradient at the point in the corner. More precisely the exact solution for is a constant except at the corner, where the same value should be chosen and the slope is not defined. The central difference approximation sets the undefined slope to the average of the left and right slopes, which yields a different limit solution. Hence the wrong calculations of the slope propagate away from the corner and form oscillations. Increasing the resolution in time only results in more oscillations, which is illustrated in [121].

Another approach is to add a viscosity term to the right hand side and thus to consider the new Hamilton-Jacobi equation

The third and best approach results in the discretizations in Sections 13.5.1 and 13.5.2, which ensures that discontinuities and fronts stay sharp. In order to achieve this for equations of the form , it is assumed in the following that the flux is convex (i.e., ). An approach introduced by S.K. Godunov [64,66,127,121] is to use the piecewise constant data at one time step to construct an exact solution by considering a local Riemann problem for each interval. The main ideas are to ensure that the conservation form of the equation is preserved, that the entropy condition is satisfied, and that the scheme is very accurate away from discontinuities. One example for such a scheme is the Engquist-Osher scheme [31,121], on which the following schemes are based. Three cases for the direction of the characteristics must be discerned when considering the properties of such a scheme: the characteristics may follow the same direction, they may meet (shock), or they may divert (rarefaction). In the shock case the Engquist-Osher scheme adds a little diffusion to the exact solution and in the other two cases it yields the exact solution.