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 :-)

Answer 2

If you want to delete a nodeA in a given kd-tree

(1) if nodeA is a leaf node ,just make it to null

(2) if nodeA is not a leaf node

Assume nodeA split by x , you have two choice

1. find the largest nodeB (whose X is the largest) in left   
2. find the minimum nodeB (whoes X is the minimum) in right  (This pdf prefer it)

Note:

if you put the nodeB equals nodeA under nodeA.right ,you should choose 2

if you put the nodeB equals nodeA under nodeA.left , you should choose 1

After that ,replace nodeA with nodeB and delete nodeB .