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?