## 3 Kd-Trees
### Cut-Off Rule  
When iterating through the tree, i.e., when determining which nodes to use in GPR, the decision to descend to a child node is determined by a cut-off rule. The design of this rule is crucial for both performance and accuracy. In our implementation, we take different criteria into consideration and define several easy to configure parameters. Working with multiple criteria and parameters has the advantage that the decision-making process is more interpretable. Furthermore, in our code implementation, we postpone more time-consuming calculations to when they are necessary. The most important criterion is how close a training point is to the node under evaluation. The cut-off rule determines whether a node is retained or the algorithm should recursively descend to the node's children. When iterating through the nodes of the tree, we evaluate every training point from the dataset one by one. When for a training point a criterion is met to descend further in the tree to the node's children, we no longer check the remaining training points. We flag the decision for a node to descend further into its children for future iterations. For the first cut-off criterion, we calculate the covariance between the node's minimum and maximum point along its widest dimension \(\mathbf{x}_{\min}\) and \(\mathbf{x}_{\max}\),  
\[\text{cov}_{\min,\,\max}=\frac{k(\mathbf{x}_{\min},\mathbf{x}_{\max})}{h} \tag{9}\]in which \(k\) is the GP kernel function and \(h\) is its height-scale for normalization. This results in a value between 0 and 1 and serves as a measurement for how wide the cuboid encapsulating the node is. If this value is above a threshold \(\text{thresh}_{\text{min,max}}\), then there is significant covariance between the two extrema. This case we are considering a node with points that are close to each other, so it is retained and the recursion is cut off. Otherwise, the algorithm continues to descend into the child nodes. This yields the first cut-off criterion:  
\[\text{cov}_{\text{min, max}}>\text{thresh}_{\text{min,max}} \tag{10}\]  
It puts an upper limit on the size we allow for the cuboids encapsulating the nodes. Cuboids that are too large make the kd-tree approximation too crude. For the second cut-off criterion, we calculate the covariance between the training point \(\mathbf{x}_{\text{data}}\) and the node's representative point \(\mathbf{x}_{\text{rep}}\). In our case, this is the nearest neighbour to the arithmetic mean of the points in the node. This representative point is pre-calculated when the tree is constructed and stored in the node itself. By using the nearest neighbour, we ensure that \(\mathbf{x}_{\text{rep}}\) is a point on the mesh:  
\[\text{cov}_{\text{data},\mathbf{x}_{\text{rep}}}=\frac{k(\mathbf{x}_{\text{ data}},\mathbf{x}_{\text{rep}})}{h} \tag{11}\]  
Again, we have an easy to interpret value between 0 and 1 that can be seen as a measurement for the distance between the node and the training point. If this value is below a certain threshold \(\text{thresh}_{\text{rep}}\), then the node is far from the training point, so it is retained and the recursion is cut off. Otherwise, we continue. This yields the second cut-off criterion:  
\[\text{cov}_{\text{data},\mathbf{x}_{\text{rep}}}<\text{thresh}_{\text{rep}} \tag{12}\]  
This puts a lower limit on the distance we allow for the nodes. Nodes that are too close are not retained, unless they are a leaf. In other words, close to the training points, we abandon the kd-tree and work with the actual test points. By including the kernel in the above criteria, it becomes part of the cut-off rule itself. The thresholds adapt to the kernel length-scale and height-scale. A downside to this approach is that these thresholds have to be recalculated every time the hyperparameters of the kernel function are updated. The first two criteria implement strict boundaries: nodes with cuboids that are too large or nodes that are too close to the data points are not retained. This means their child nodes are always visited.