Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Closest Pair | Reply
I don't understand one part of the explanation on how to solve the closest pair problem. As bmerry says, you store the points in a balanced binary tree by y coordinate. He also says that when h is decreased or the next point is processed, you remove all the points that are more than h away by x coordinate. How is this done efficiently on a binary tree sorted by y coordinate? If you can't do it efficiently and have to process every point, wouldn't that make the entire binary tree useless and give the same runtime as a normal array? Someone please explain.
Re: Closest Pair (response to post by klopyrev) | Reply
Um... nvm! I got it!
Re: Closest Pair (response to post by klopyrev) | Reply
I can't get it. How do you remove points farther than h(by x coordinate) when the set is ordered by y?

Thanks in advance.

BTW, I am curious why is that minus here? Is it a bad thing, if there is something unclear to ask? IMHO, I think that is the purpose of the forums. I can't understand also why Klopyrev's post is also minused.
Re: Closest Pair (response to post by petar1) | Reply
Build another set having elements sorted by x coordinates.

Find the element having highest x value but less than nx-h (where nx is the x value of new point) in log(size).

Remove all elements upto this (including it) from the set and simultaneously search and remove the corresponding elements from the other set(the one sorted by y value) in log(size).
Re: Closest Pair (response to post by quanchi) | Reply
Thanks for your help. I got it:)

But I thinked of a way without using a second set. Just have two indexes left and right. They are pointing into the array with the points ordered by x. They surround the elements which are in the set ordered by y. When you add a point to the set just increment right and when you remove element from the set just increment left.

I think it is easier and better to do it this way.
And I have checked it. It works:)
Re: Closest Pair (response to post by petar1) | Reply
I find this article really hard to follow...

bmerry wrote

"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.