# closest pair in N-Dimensional

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.

-
add comment

## 1 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.

-
Could you can give me the 3D as an example? I still not very clear about it, what the sparsity do with the problem. –  Liang-Yu Pan May 2 '13 at 14:38
Beware that 2D or 3D shouldnt change much! Sparsity just means a low expected number of points in the slab (of course one could construct "pathologic" or particular counterexamples anyway), so that the algorithm complexity will be low in practice on random input (that is on average, not in the worst case). If you have few points in the slab (say of the order of $d \cdot \sqrt[D/(D-1)]{N})$, then also finding the closest pair will be fast. –  Quartz May 2 '13 at 17:52
add comment