13.3.1 The Boundary Value and the Initial Value Formulation

There are two formulations for the description of moving boundaries as solutions of partial differential equations.

In the boundary value formulation the PDE $F(t,\mathbf{x}) \Vert\nabla_\mathbf{x}u\Vert = 1$ has to be solved. The surface in question is the set $\{ \mathbf{x}\in\mathbb{R}^n \mid T(\mathbf{x})=t \}$. Here the speed function $F$ must be positive. For our general application domain where both etching and deposition shall be simulated, the restriction $F\ge0$ for the speed function is not acceptable. Thus they are not used for tracking surface evolution, but they are important for constructing the signed distance function from the surface, since the signed distance function is the solution of the special problem $\Vert\nabla_\mathbf{x}u\Vert = 1$, where $F(t,\mathbf{x})=1$, and will be needed in Section 13.6.

Fast marching methods are a means for efficiently numerically solving this boundary value problem [119,120,121]. Usually an iterative approach would be used. The main observation of the fast marching method is, however, that the solution can be constructed point by point using only upwind values so that each grid point basically has to be touched only once. The grid points are partitioned into three sets, namely the set of known points, of trial points, and of far away points. First the known points are initialized. Their neighboring, trial points are assigned tentative values using a suitable discretization and all other points are called far away points. The main observation is that the trial point with the smallest value was already assigned its correct value and it is thus promoted a known point. Here the algorithm repeats until all points are known. By storing the trial points in a heap data structure [113] the main observation can be fully exploited.

In the initial value formulation the PDE $u_t + F(t,\mathbf{x}) \Vert\nabla_\mathbf{x}u\Vert = 0$, where $u(0,\mathbf{x})$ is given, has to be solved. Here the surface in question is $\{ \mathbf{x}\in\mathbb{R}^n \mid u(t,\mathbf{x})=0\}$. No restriction on the speed function is required. This approach gives rise to the particular level set methods which are the topic of this chapter.