## 2 kd-TreeData Structure for Cell Subdivision
### Comparison with Quad/Oct-Tree  
Here, the kd-tree structure is compared with quad-tree and oct-tree in the following three aspects:  
1. _Number of Quadrature Sub-cells Generated_: Table 1 summarizes the worst-case and best-case ratios of the number of sub-cells generated by kd-tree to that generated by quad/oct-tree. In the worst-case scenario, the immersed boundary is sufficiently complex that all of the cells have to be completely subdivided in each level. Therefore, the number of sub-cells generated by kd-tree subdivision is the same as that generated by quad-tree and oct-tree. The best-case ratio is proven in Theorem 1. **Theorem 1**: _Given an arbitrary immersed boundary, the number of sub-cells generated by kd-tree subdivision is no smaller than two-thirds of that generated by quad-tree, and three-sevenths of that generated by oct-tree._  
Proof. : The minimum kd-tree splits of a 2D and a 3D cell are illustrated in Figure 4. A complete single-level 2D subdivision operation increases the number of sub-cells  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Input:**  Cell \(C\), depth of tree \(depth\), splitting direction vector \(dir\) and auxiliary flag \(nocheck\)  
**Output:**  kd-tree \(v\) containing quadrature sub-cells in leaves  
1:functionBuildKdTree(\(C\), \(depth\), \(dis\), \(nocheck\))
2:if\(depth\ mod\ Dim=0\)then\(\triangleright\) Reinitialize at the first depth of each level
3:\(dir\leftarrow[x,y](2D)\) or \([x,y,z](3D)\)
4:\(nocheck\gets false\)
5:endif
6:\(SplitDir\gets dir(1)\)\(\triangleright\) Set the first element in \(dir\) as the default splitting direction
7:if\(nocheck=false\)then
8:if C not intersect boundary or \(depth=MaxDepth\)then
9:return leaf containing \(C\)
10:elseif\(length(dir)\geq 2\)then\(\triangleright\) No further check is needed if only one direction is available
11:for\(i\gets 1,length(dir)\)do
12:\(nocheck\gets true\)
13:if Splitting line(2D)/plane(3D) in \(dir(i)\) not intersect boundary then
14:\(nocheck\gets false\)
15:\(SplitDir\gets dir(i)\)
16:endif
17:endfor
18:endif
19:endif
20:\(C^{\prime}_{half}\),\(C^{\prime\prime}_{half}\leftarrow\) Split \(C\) in \(SplitDir\)
21:\(dir_{new}\leftarrow\) Exclude \(SplitDir\) from \(dir\)
22:\(v_{left}\leftarrow\) BuildKdTree(\(C^{\prime}_{half}\), \(depth\)+1, \(dir_{new}\), \(nocheck\))
23:\(v_{left}\leftarrow\) BuildKdTree(\(C^{\prime\prime}_{half}\), \(depth\)+1, \(dir_{new}\), \(nocheck\))
24:return\(v\) with two branches \(v_{left}\) and \(v_{right}\)
25:endfunction ```  
**Algorithm 2** Algorithm for building kd-tree data structure. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Problem Dimension** & **Worst Case** & **Best Case** \\ \hline
2D (\(N_{\text{2d-tree}}/N_{\text{quad-tree}}\)) & \(1\) & \(2/3\) \\
3D (\(N_{\text{3d-tree}}/N_{\text{oct-tree}}\)) & \(1\) & \(3/7\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Worst-case and best-case ratios of the number of sub-cells generated by kd-tree, quad-tree, and oct-tree. by \(4-1=3\), whereas an incomplete single-level 2D subdivision only increases it by \(3-1=2\). Assume that the total number of complete and incomplete subdivision operations is given by \(S_{c}\) and \(S_{i}\), respectively. The total number of sub-cells in a 2D tree is provided by  
\[N_{\text{2d-tree}}=1+3S_{c}+2S_{i}. \tag{1}\]  
Next, assume that the total number of subdivisions is \(S_{\text{total}}\). If \(S_{c}=S_{\text{total}}\) and \(S_{i}=0\), the kd-tree degenerates to a quad-tree, i.e.,  
\[N_{\text{quad-tree}}=1+3S_{\text{total}}. \tag{2}\]  
Given an arbitrary immersed boundary, the \(N_{\text{2d-tree}}/N_{\text{quad-tree}}\) ratio is provided by  
\[\frac{N_{\text{2d-tree}}}{N_{\text{quad-tree}}}=\frac{1+3(S_{\text{total}}-S _{i})+2S_{i}}{1+3S_{\text{total}}}\geq\frac{1+2S_{\text{total}}}{1+3S_{\text{ total}}}>\frac{2}{3}. \tag{3}\]  
Likewise, a complete single-level 3D subdivision operation adds \(8-1=7\) sub-cells. However, the number of sub-cells added by an incomplete 3D subdivision may vary from 3 to 6.