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

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