Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.