Maximum and Minimum distance from query point within bounding box

Question

I'm reading an article regarding approximating sums using KD-trees (similar to FMM).

As part of the effort I'm trying to make sense of this article , which is cited.

I'm having trouble understanding this part:

Computing the maximum variation of weights over all points below node ND is easy. We know the location of xquery and we know the bounding hyperrectangle of the current node. A simple algorithm costing O(Number of tree dimensions) can compute the shortest and largest possible distances to any point in the node. From these two values, and the assumption that the weight function is non-increasing, we can compute the minimum and maximum possible weights wmin and wmax of any datapoint below node ND.

The only solution I can think of is to bound the variation (wmax-wmin) from above using the corners of the bounding box, and then computing the distance from the query point to each of the corners is indeed O(d), but there are 2^d corners... But this doesn't seem to be the author's intention. Could anybody point me to what I"m missing here?

Answer 1

For the maximum distance it is indeed $O(d)$ where $d$ is the number of dimensions. You only need to test one dimension at a time. If the hyper-rectangle's extent along dimension $i$ is from $H_{i,0}$ to $H_{i,1}$. You test whether $|x_i - H_{i,0}| > |x_i - H_{i,1}|$. If the answer is true, you only need to test half of the remaining corners, only the ones with the $i$'th coordinate equal to $H_{i,0}$, if the answer is false, then the coordinate should be $H_{i,1}$. After testing for $i \in \{0...(d-1)\}$ you get the coordinates of the farthest corner from $x$.

There's no easy way to get an estimate for the lowest possible distance if $x$ is inside the bounding hyper-rectangle, indeed the lowest we can get is simply 0.

If $x_{query}$ is outside the node's bounding hyper-rectangle, you can find the distance from the hyper-rectangle, that would be an estimate for the lowest possible distance. $x_{query}$ may have some of its coordinates inside the extent and some of them outside, you'll need to find a distance from some hyper-plane defined by some of the corners as follows:

Suppose:

$K = \{i \in \{0...(d-1)\} | H_{i,0} < x_i < H_{i,1}\}$, $J_0 = \{i \in \{0...(d-1)\}\ \ \ |\ \ \ |H_{i,0} - x_i| > |H_{i,1} - x_i|\text{ and } x \notin K \}$ and $J_1 = \{i \in \{0...(d-1)\}\ \ \ |\ \ \ |H_{i,1} - x_i| > |H_{i,0} - x_i|\text{ and } x \notin K \}$

The distance from that hyper-rectangle will be $\sqrt{\sum_{i\in J_0}(x_i-H_{i,1})^2 + \sum_{i\in J_1}(x_i-H_{i,0})^2}$