13.3.2 Methods for Speeding Up the Solution of the Level Set Equation

Here the advantages and disadvantages of numeric approaches to solving the level set PDE are discussed and the reasons for the algorithm devised in Section 13.6 are given.

The following main approaches to increase accuracy while decreasing computational effort are known. They are all based on solving the underlying equations efficiently by using adaptive schemes. Among more sophisticated algorithms are narrow band level set methods, adaptive level set methods, and triangulated level set methods for the initial value formulation and fast marching methods for the boundary value formulation.

The first method is adaptive mesh refinement on a rectangular grid. The problem here are the interfaces between fine and coarse cells, especially the updates of so called hanging nodes. This problem is inherent to mesh refinement on rectangular grids.

The second method is to use triangular unstructured meshes. The advantages of this methods are that adaptive mesh refinement is possible without introducing hanging nodes and that interfaces to non-planar surfaces, which occur frequently in applications, can be much better described than by rectangular meshes. On the other hand adaptive mesh refinement on unstructured meshes necessitates suitable algorithms for refining and coarsening the mesh as the surface moves. Furthermore there is no reason why any calculations should be performed for points far away from the zero level set at all, since these points do not have any influence.

This last observation leads to narrow band algorithms: it suffices to consider only active grid points within a narrow band of the zero level set. The width of the narrow band is usually predefined and fixed and should be as small as possible. As the zero level set moves, some points fall out of the narrow bands and some points become active and enter the narrow band. Thus the question arises how to determine the active points in the narrow band. The usual approach [122] is to choose a new narrow band whenever the front hits the boundary of the current narrow band, i.e., to reinitialize the narrow band and the signed distance function every few steps. The disadvantage of this method is that the right balance between the width of the narrow band and the frequency of reinitializations is not obvious. The algorithm devised in Section 13.6 uses a different idea. There the active narrow band is determined in each step by using the distance information that is computed in the course of extending the speed function.

Narrow banding provides a substantial speed up. In two dimensions, the computational effort is reduced from $O(n^2)$ to $O(n)$ and in three dimensions from $O(n^3)$ to $O(n^2)$ compared to fixed grids on fixed simulation domains.

In the ELSA simulator (cf. Section 13.8) the level set algorithm includes narrow banding, since this approach provides the most benefits. A fast marching algorithm is not used directly for tracking surfaces, but it occurs as an auxiliary method for constructing the signed distance function (cf. Section 13.6).