||I find this article really hard to follow...
"Suppose that we have processed points 1 to N − 1 (ordered by X) and the shortest distance we have found so far is h."
Are we scanning left to right? Shortest distance, does this include diagonal distance? Ordered by X, does this mean sort all the X-points from lowest to highest before processing?
"We now process point N and try to find a point closer to it than h."
Point N is marked pN on the diagram, at least I think it is. A point closer to it than h, does that mean all points inside the circle radius h with center N? As written it seems like the only points that could be 'h' away are above and below N on the same Y axis, is this correct?
"We maintain a set of all already-processed points whose X coordinates are within h of point N, as shown in the light grey rectangle."
Surely you mean the dark gray rectangle? All points in the light gray are further than 'h'? How can we have already processed points within h of N if we havn't got to N yet?
"As each point is processed, it is added to the set, and when we move on to the next point or when h is decreased, points are removed from the set."
Man I need a table or something this just does not compute at all. What are the criteria for removing a point? How do we know h has decreased? Added to the set, is the set a Red Black tree?
"The set is ordered by y coordinate."
What? There must be something in the set nodes I don't know about. Can you give a quik note on the contents of a node. What does the highest node in the set represent?
"A balanced binary tree is suitable for this, and accounts for the log N factor."
My previous questions will probably clear this up.
The article has some things I really want to learn but the rest of the article is equally cryptic. The diagrams help a lot but the text along with the diagrams is too sparse. My guess is most people scan the diagrams and move along. I want a deeper understanding.