## Reinitialization

As noted in the introduction to this chapter, there are two means by which the level set method can be kept stable for arbitrary speed functions. For nearly all applications of the level set method, one of these techniques must be used. One method involves using velocity extensions, and the other uses reinitialization. Both methods are frequently used, and there is disagreement as to which method is preferred. Recent advances in the level set method have resulted in either method producing good results. For balance, both methods are presented, with reinitialization treated here and velocity extensions to follow in Section 4.2.5.

Reinitialization was first introduced in [19], where it was observed that the only part of the level set function which is of interest is the portion immediately around the zero level set. While initially, the level set function can be constructed to be the signed distance function to the interface, most speed functions, F , will not preserve this property over time. This can lead to instability, and ultimately failure of the method. Reinitialization is, therefore, a process where the level set function is reconstructed to be the signed distance function.

Let 0 be the level set function, and let 0 be the desired reconstructed level set function, then 0 solves

This pair of equations is precisely the type of problem the fast marching method is designed to solve, with F = 1 in Eq. 4.21. Furthermore, the function 0 can be used to initialize the fast marching method, as described in Section 4.2.3. The solution 0) of Eqs. 4.29 and 4.30 is now called reinitialized.

Early implementations of reinitialization suffered from accuracy, particularly in regions of high curvature. When the interface was reinitialized, there was significant error in the computed solution in Eq. 4.29. This was primarily due to the low-order accurate methods used for interpolating 0. More recent methods, such as the one presented in Section 4.2.3, significantly reduced this error, as illustrated in Fig. 4.8.

It has been observed recently [100] that for the specific application of reinitialization, it is not necessary to use the heap sort method. In fact, the same results can be achieved by simply taking a first-in-first-out strategy for the order of the grid points. In other words, instead of maintaining the binary tree and

Figure 4.8: Comparison of modern and original reinitialization results for a coarsely meshed circle. The exact solution and the modern reinitialization method are nearly overlapping. This figure reprinted from [22].

continually sorting the nodes, it is sufficient to simply take points out of the set T in the same order in which they entered. The only exception is that the initial set of grid points in the set T should still start out sorted. This observation is of interest because it reduces the computational complexity of the fast marching method from O (N log N) to simply O (N) where N is the total number of grid points.