I have to find the closest pair in n-dimension, and I have problem in the combine steps.
I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find the smallest distance in left and right part respectively, dr, dl.
And then dm=min(dr,dl); And I have to consider the across hyper-plane constructed by median x, and the cloest pair must be in in the 2d think slab, and I don't understand that what to do in the following?(How to reduce the dimension)
Here is the ppt that I following, please explain that the combine step, I have read it for a day and still cannot figure it out what it is doing.(from p9)
https://docs.google.com/file/d/0ByMlz1Uisc9OWmxBRUk1LW9oMlk/edit?usp=sharing
Thx in advance.
Best Answer
The closest pair was either already found, or is in the 2-d-thick slab which can only include a low number of points. No need to reduce the dimension, just apply the algorithm recursively left, right and on the slab (cycling the direction the separating hyperplane is perpendicular to), optimality is implicit. Here are other slides.