# Efficient and Scalable Initialization of Partitioned Coupled Simulations with preCICE
## 3 R-Tree-Based Mesh Filtering
The Boost.geometry data structure provides \(k\)-nearest-neighbor queries, which the nearest-neighbor mapping and the nearest-projection mapping require, in \(O(k\log(n))\). The data structure also allows for bounding box queries, which the radial-basis-function mapping requires, in \(O(\log(n))\). Let the dimension \(d\) be 2 or 3. The search mesh has a vertex set \(V^{S}=\{v_{i}^{S}\in\mathbb{R}^{d};\)\(i=1,2,\ldots,n_{\mathcal{D}}^{S}\}\) and a mesh connectivity information given by an edge set \(E^{S}\) with size \(n_{v}^{S}=|E^{S}|\) and a triangle set \(T^{S}\) with size \(n_{t}^{S}=|T^{S}|\) for \(d=3\). We further use \(n^{S}:=n_{v}^{S}+n_{c}^{S}+n_{t}^{S}\). The origin mesh has a vertex set \(V^{O}=\{v_{i}^{O}\in\mathbb{R}^{d};i=1,2,\ldots,n_{v}^{O}\}\). Nearest-neighbor mapping and radial-basis-function mapping operate on vertices only. Thus, it is beneficial to store each set of primitives of the search mesh (\(V^{S}\), \(E^{S}\), \(T^{S}\)) in a separate index tree to avoid overhead. A **nearest-neighbor data mapping** searches for the nearest vertex in \(V^{S}\) for each vertex of \(V^{O}\). This requires to insert all vertices of \(V^{S}\) into the R-tree resulting in a complexity of \(O(n_{v}^{S}\log(n_{v}^{S}))\). Afterwards, we query for the nearest-neighbor of each vertex of \(V^{O}\) at a total cost of \((n_{v}^{O}\log(n_{v}^{S}))\). A **nearest-projection data mapping** searches for the nearest primitive (vertex, edge, or triangle) of \(V^{S}\) for each vertex of \(V^{O}\). We use a cascading scheme: For \(d=3\) (see Figure 4), the mapping attempts to first find an orthogonal projection onto a triangle, if this  
Figure 3: Comparison of the nearest-neighbour mapping (**top**) and the nearest-projection mapping (**bottom**). Both mappings are consistent and map from the search mesh \(M^{S}\) to the origin mesh \(M^{O}\). The nearest-projection mapping prevents extrapolation by mapping to the closest vertex for \(v_{1}^{O}\) and \(v_{4}^{O}\). The vertices \(v_{2}^{O}\) and \(v_{3}^{O}\) are projected onto the edges \((v_{1}^{S},v_{2}^{S})\) and \((v_{2}^{S},v_{3}^{S})\), resulting in interpolation. fails, it tries to compute an orthogonal projection onto an edge, and finally, if this also fails, selects the closest vertex. For \(d=2\), the above method starts at projecting onto an edge. For a more precise description, let us categorize primitives by their degree: \(1,2,3\) for vertices, edges, and triangles, respectively. Then, a nearest projection of degree \(1\) of a vertex \(v^{S}\) is simply a nearest-neighbor search. More interestingly, to find the nearest projection of degree \(m=2\) or \(m=3\) of \(v^{S}\),  
1. we fetch the \(k\) nearest primitives of degree \(m\) of vertex \(v^{S}\),
2. we sort them by ascending distance to \(v^{S}\),
3. we process the list of primitives and calculate interpolation weights \(w_{1},\ldots,w_{m}\) for data interpolation from the primitive's vertices to the projection point on the respective plain or line,  
we terminate and **return** the current primitive, if all weights are positive \(w_{i}\geq 0\)\(\forall i=1,\ldots,m\),
4. we **return** the nearest projection of degree \(m-1\) of vertex \(u\) if no valid projection of degree \(m\) could be found. This cascading scheme requires to probe all primitives and, thus, to index the complete search mesh in an R-tree. This is of total complexity  
\[O(n_{v}^{S}\log n_{v}^{S}+n_{e}^{S}\log n_{e}^{S}+n_{t}^{S}\log n_{t}^{S}). \tag{1}\]  
In the best case, the cascading algorithm will only probe primitives with the highest dimension. Therefore, only the R-tree index for said primitives is required for the mapping. As we only generate the R-tree structure for lower dimensional primitives if required, the best case total cost is  
\[O(\underbrace{n\log n}_{\text{insertion}}+\underbrace{n_{v}^{O}\cdot k\log n}_{ \text{query}}),\ n= \begin{cases}n_{e}^{S},&d=2\\ n_{t}^{S},&d=3\end{cases} . \tag{2}\]