Deleting an element from a kd-tree of two dimensions.

Question

I would like to extend a kd-tree (2D) class to be able to remove nodes (points). This removal should be conducted without having to rebuild large sections of the tree. The algorithm described in these slides, on slide 13 seems to be what I am after. However, I am trouble following the description of "findmin()" found on slide 7, which is utilized in the node removal algorithm.

Questions

1. What does the "i" mean on the second to last line? (Maybe this is a mistake by the author, as it is not referenced elsewhere?)

2. What exactly is "whichAxis"? Is it the depth of the splitting hyperplane we want to get nearest to?

3. What is "minimum()", minimizing? I though this would be the distance to the axis, but it looks to me like the author is minimizing the points, which doesn't make sense to me.

Answer 1

(1) I think i is a typo; I don't have anything like that in my implementation of it, and it appears to work fine (famous last words..).

(2) whichAxis is the plane you're searching for the minimum in. So in two-dimensional data, it'll be either x or y. E.g. for points (20,40) and (40,20), one is the minimum in x and the other in y. When you start searching for a replacement node, you should know which splitting plane you have to search in.

(3) The slide is written a little strangely. You want to find the minimum value in the appropriate plane. Maybe this will clarify a little (c#). My implementation is for a dataset using eastings and northings as x and y. minAxis is just a bool, as I only ever have two planes.

bool winner = minAxis ? (left.Easting < right.Easting) : (left.Northing < right.Northing);
return winner ? left : right;

...where left and right are the minimum values recursively searched for from the left and right child trees of the node we're in. I can post the full function if it makes it clearer :-)