# Overset Grid Assembler and Flow Solver with Adaptive Spatial Load Balancing
## 5 Core Algorithm  
In the first time step, the donor search is performed with alternating digital tree (ADT) [17], which is a space partitioning binary tree. ADT tree splits the spatial domain into halves with axis-aligned cutting planes, recursively. The axis of cutting plane alternates in cyclic order in accordance with the levels in ADT. In three-dimensional space, there are three cutting planes with cutting axes parallel to the \(x\)-, \(y\)-, and \(z\)-axis. The position of the cutting plane along the cutting axis depends on the number of dimensions required to define an object to be inserted. For example, if a point (0D) is to be inserted to an ADT, positions of cutting planes would be (\(x\), \(y\), \(z\)) coordinates of the point along the respective cutting axes. Moreover, if the inserted object is a rectangle, the positions of cutting planes would be the six (\(x_{min}\), \(y_{min}\), \(z_{min}\), \(x_{max}\), \(y_{max}\), \(z_{max}\)) dimensions of the rectangle in the respective orientations of the cutting plane. In general, objects to be inserted to ADT are n-orthotopes or hyperrectangles. In the example above, point and rectangle are 1- and 2-orthotopes. In this work, the objects are AABB, which is 3-orthotope, of mesh cells. Therefore, both the domain and objects to be inserted are six-dimensional. For visualization of the insertion operation into ADT, Figure 3 demonstrates the insertion of points into ADT in two-dimensional space. On the root level, point A is the median in the \(x\)-axis, and it is associated with the whole domain, \(\Omega_{A}\). Domain \(\Omega_{A}\) is divided by a plane with cutting axis parallel to the \(x\)-axis at point A. Next, the cutting axis is changed to be the \(y\)-axis. Point B, which is one of the points in the left half of \(\Omega_{A}\) and is the median in the \(y\)-axis, is assigned to \(\Omega_{B}\), which is the left half of \(\Omega_{A}\). Point C is inserted similar to Point B except that it belongs to the right half of \(\Omega_{A}\). The rest of the points are inserted into sub-branches of the tree in the same fashion. The search operation on ADT is similar to insertion. Given a query point, AABBs which overlap the query point are returned. If the query point is outside the hypercube of the ADT, the search operation returns an empty array, meaning that none of AABBs in the tree overlaps the query point. Assuming that the query point is inside the hypercube of the tree, the search operates recursively by always starting from the root node. First, it is tested whether the query point is contained by the AABB in the current node. If so, the AABB is added to the array which is to be returned after the recursive search operation is completed. Regardless of containment of the query point by the AABB, the query point is redirected to one or both halves of the current node by testing the dimension of the query point against the cutting axis associated with the current level. that the geometric shape of mesh cells are polyhedra which are not axis-aligned in an unstructured grid. However, ADT accepts only axis-aligned objects to be inserted. Therefore, given a mesh block, \(M_{i}\), AABB and associated ID of each mesh cell are inserted into the respective ADT \(T_{i}\). Once an ADT tree is constructed for every mesh block, the candidate donor cell for each mesh cell in \(M_{i}\) is searched out by providing the centroid (query point) of the cell as input to all trees \(T_{j}\) where \(j\
eq i\). As the output of search operation, each tree \(T_{j}\) returns an array of IDs corresponding to the mesh cells in \(M_{j}\). The query point is tested for containment by each polyhedron corresponding to the returned ID. The mesh cell which contains the query point is added to the list of candidate donors. The procedure is shown in Algorithm 1.