## 4 Local Refinement Near Immersed Boundaries Using Algebraic Level Sets
### Numerical Examples  
The efficiency and robustness of the proposed algorithms are demonstrated below through several numerical examples. Figure 16 shows a seven-level hierarchical refinement of a square domain with respect to a rectangular immersed boundary. The computational cost as a function of the number of levels is listed in Table 5. The hierarchical mesh generation only takes tens of microseconds on a desktop personal computer, even for a very large number of levels.  
Figure 15: (**a**) Determination of level \(l\) cut cells using the sign-based criterion. A cut cell is missed due to the small feature size. (**b**) Determination of level \(l\) cut cells using the distance-based criterion, followed by sign-based subdivision to generate the level \(l+1\) cut cells. For a cell size \(d_{\text{cell}}=1\), the distances of the \(C_{5}^{l}\) vertices to the boundary are annotated in the figure.  
In order to include a larger local refinement region, it may be desirable to refine both the cut cells and their \(i\)th neighbors. As illustrated in Figure 17, the order \(i\) controls the bandwidth of a single level mesh. In contrast to level-wise hierarchical refinement, refinement within a level is referred to as _horizontal refinement_. A two-dimensional example of horizontal refinement is shown in Figure 18.  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Number of Levels** & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
**Time Cost** (\({}^{\circ}\)s) & 0.1 & 0.7 & 1.4 & 3.2 & 6.8 & 14.8 & 36.7 \\ \hline \hline \end{tabular}
\end{table}
Table 5: Computer time on a personal computer required for hierarchical refinement of the geometry shown in Figure 16.  
Figure 16: A two-dimensional seven-level hierarchical refinement of a square domain with respect to a rectangular immersed boundary: (**a**) hierarchical mesh and (**b**) sub-meshes in each level.  
Figure 17: Schematic of horizontal refinement: (**a**) the neighbors of a cut cell provide a larger refinement region, while (**b**) the union of the neighbors forms a refinement band.  
Figure 18: Horizontal refinement with different bandwidth. (**a**) Only the cut cells are refined. (**b**) First-order refinement: the cut cells and their first nearest neighbors are refined. (**c**) Second-order refinement: the cut cells and up to their second nearest neighbors are refined.  
The mesh refinement algorithms and kd-tree data structure can be directly extended to three-dimensional problems thanks to their dimension-independent nature. Figure 19 shows a six-level hierarchical refinement of a cubic domain in the presence of an ellipsoidal boundary. The computational cost of refinement is summarized in Table 6. Compared to the time cost during matrix assembly and system solution generation, the sub-second mesh generation time is almost negligible.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Number of Levels** & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
**Time Cost** (\({}^{\circ}\)s) & 0.1 & 2.4 & 8.6 & 47.9 & 166.3 & 434.8 \\ \hline \hline \end{tabular}
\end{table}
Table 6: Computer time on a personal computer required for hierarchical refinement of the geometry shown in Figure 19.  
Figure 19: A three-dimensional six-level hierarchical refinement of a cubic domain with respect to an ellipsoidal boundary: (**a**) hierarchical mesh and (**b**) sub-meshes in each level.