6.6.3 Choice of the Interpolating Equation



next up previous contents index
Next: Locality and Monotonicity Up: 6.6 Interpolation Previous: 6.6.2 Architecture

6.6.3 Choice of the Interpolating Equation

A natural initial approach is to choose the Laplace equation

 

with the ``internal Dirichlet boundary condition''

 

for all source grid points where the attribute value is known, and the Neumann boundary condition

 

for all other (non-Dirichlet) boundary points.

When only boundary values are known and all of the inner grid points are unknown, the problem is the classical Dirichlet problem. In our case, however, there are known values on inner grid points as well. Let the grid contain grid points comprised by unknown and known (Dirichlet) values, . The discretization of Equation 6.5 will then lead to to a system of equations for the unknown .

The Delaunay graph and the Voronoi polygons can be readily used to discretize Equation 6.5. With a finite-difference approximation and a box integration over the Voronoi regions, one directly obtains a linear system for the unknown values . The Neumann boundary conditions are fulfilled implicitly by the box integration. The Dirichlet values cause a non-zero right-hand side of the linear system.

As Equation 6.5 is generally not fulfilled at the Dirichlet points (the source grid points), spikes may form at the source grid points where originally.

In Figures 6.29 to 6.32 a comparison of the Laplace and biharmonic interpolation is presented using a practical ion-implanted Boron doping profile. Contour lines are generated using linear interpolation on the respective grid for

 

The original doping profile (Figure 6.29) has been generated on a dense tensor product grid (the grid is shown in Figure 6.25), then the profile has been interpolated (using a proven two-dimensional cubic spline interpolation [137] [138] on the dense grid) onto the comparatively coarse triangular grid generated by Trigen [113] (the grid is shown in Figure 6.26). The resulting interpolated profile on the Trigen grid is shown in Figure 6.30. This profile has been used as Dirichlet values for the interpolation onto the dense merged triangular grid (Figure 6.27) to evaluate the quality of the interpolation method.

  
Figure 6.30: Doping profile interpolated onto the coarse triangular grid.

In this interpolation step from a coarse onto a very fine grid, 21% of the new (merged) grid points are Trigen grid points and define the Dirichlet values, 77% are grid points from the dense tensor product grid, and 2% are inserted by the boundary refinement step. Hence, 79% of the merged grid points are interpolated.

The profile shown in Figure 6.31 was interpolated using the Laplace equation and Figure 6.32 was interpolated using the biharmonic equation. Note the jagged contours and the decay of the peak in Figure 6.31.

  
Figure 6.31: The solution of the Laplace equation

  
Figure 6.32: The solution of the biharmonic equation

Besides the smoother interpolation provided by the biharmonic equation, the peak which is present in the original profile (Figure 6.29), although badly discretized in the coarse Trigen grid, is fairly well reconstructed when the biharmonic equation is used (Figure 6.32). This example shows that the reconstructive biharmonic interpolation method is superior with respect to a straightforward linear interpolation on the coarse triangular grid.





next up previous contents index
Next: Locality and Monotonicity Up: 6.6 Interpolation Previous: 6.6.2 Architecture



Martin Stiftinger
Thu Oct 13 13:51:43 MET 1994