## 3 kd-Tree Data Structure for THB-Spline Refinement
### Brief Review of Truncated Hierachical B-Splines  
Define a sequence of \(k\)-variate B-spline bases \(B^{l},l=0,1,\ldots,L-1\) satisfying the following nesting relation:  
\[\text{span}\,\mathcal{B}^{0}\subset\text{span}\,\mathcal{B}^{1}\subset\cdots \subset\text{span}\,\mathcal{B}^{L-1}. \tag{6}\]  
Thus, any lower-level B-spline basis function \(N_{i}^{l}\in\mathcal{B}^{l},l=0,1,\ldots,L-2\) can be represented by a linear combination of higher-level B-spline basis functions \(N_{j}^{l+1}\in\mathcal{B}^{l+1}\) as follows:  
\[N_{i}^{l}=\sum_{\text{supp}\,N_{j}^{l+1}\subset\text{supp}\,N_{i}^{l}}\alpha_{ j}N_{j}^{l+1}. \tag{7}\]  
For the case of one-dimensional dyadic refinement (i.e., the knot vectors are uniform and each knot span is halved from \(V^{l}\) to \(V^{l+1}\)), Equation (7) takes the form:  
\[N_{i,p}=2^{-p}\sum_{j=0}^{p+1}\binom{p+1}{j}N_{2i-1+j,p}^{l+1} \tag{8}\]  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Tree Type** & \(N_{\text{\emph{subcell}}}\) & **Ratio of \(N_{\text{\emph{subcell}}}\)** \\ \hline
2D tree & 48 & \\ Quad-tree & 61 & 0.787 \\ \hline
3D tree & 521 & 0.722 \\ Oct-tree & 722 & 0.722 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Comparison of kd-tree and quad/oct-tree subdivision in the presence of a hyper-spherical boundary as shown in Figure 6.  
Figure 6: kd-tree subdivision of a unit cell in the presence of (**a**) a quadrant and (**b**) a one-eighth spherical surface. The hyper-spheres are centered at a corner and have a radius of \(R\). The maximum level is four in both examples. The domain color represents a signed distance to the immersed boundary.  
where \(p\) is the degree of the B-spline. We further define a sequence of nested domains  
\[\Omega^{0}\supseteq\Omega^{1}\supseteq\cdots\supseteq\Omega^{L-1} \tag{9}\]  
where each \(\Omega^{l}\in\mathbb{R}^{k}\) represents a \(k\)-dimensional refinement region at level \(l\) and its boundary \(\partial\Omega^{l}\) is aligned with the knot grid of \(\mathcal{B}^{l-1}\). A two-dimensional hierarchical mesh example is shown in Figure 7.  
The hierarchical B-spline basis \(\mathcal{H}\) is defined as  
\[\mathcal{H}=\bigcup_{l=0}^{L-1}\Big{\{}N^{l}\Big{|}N^{l}\in\mathcal{B}^{l} \wedge\text{supp}\,N^{l}\subseteq\Omega^{l}\wedge\text{supp}\,N^{l}\
subseteq \Omega^{l+1}\,\Big{\}}. \tag{10}\]  
As illustrated in Figure 8a, the hierarchical B-spline basis functions do not satisfy the partition of unity property. [PERSON] et al. (2020) proposed a truncation operator to remove the higher-level B-spline components from a current-level basis function:  
\[\text{trunc}^{l+1}\,N^{l}_{i} =N^{l}_{i}-\sum_{\begin{subarray}{c}\text{supp}\,N^{l+1}_{i} \subset\text{supp}\,N^{l}_{i}\\ \text{supp}\,N^{l+1}_{j}\subseteq\Omega^{l+1}\end{subarray}}\alpha_{j}N^{l+1 }_{j} (\text{Subtractive Representation}) \tag{11a}\] \[=\sum_{\begin{subarray}{c}\text{supp}\,N^{l+1}_{i}\subset\text{ supp}\,N^{l}_{i}\\ \text{supp}\,N^{l+1}_{j}\
ot\subseteq\Omega^{l+1}\end{subarray}}\alpha_{j}N^{l +1}_{j} (\text{Additive Representation}). \tag{11b}\]  
The general THB-spline basis \(\mathcal{T}\) can be constructed as follows:  
\[\mathcal{T}=\bigcup_{l=0}^{L-1}\Big{\{}\tilde{N}^{l}\,\Big{|} \tilde{N}^{l} =\text{trunc}^{L-1}\cdots\text{trunc}^{l+2}\,\text{trunc}^{l+1}\,N ^{l},\] \[N^{l} \in\mathcal{B}^{l}\wedge\text{supp}\,N^{l}\subseteq\Omega^{l} \wedge\text{supp}\,N^{l}\
subseteq\Omega^{l+1}\Big{\}}. \tag{12}\]  
Figure 7: A two-dimensional four-level dyadic hierarchical mesh: (**a**) the nested domains contain level-wise sub-meshes; (**b**) the sub-meshes are overlaid to generate the hierarchical mesh.