What is wrong with my logic for the divide and conquer algorithm for Closest pair problem?
Posted
by
Programming Noob
on Programmers
See other posts from Programmers
or by Programming Noob
Published on 2012-07-03T23:03:36Z
Indexed on
2012/07/04
3:22 UTC
Read the original article
Hit count: 255
algorithms
I have been following Coursera's course on Algorithms and came up with a thought about the divide/conquer algorithm for the closest pair problem, that I want clarified.
As per Prof Roughgarden's algorithm (which you can see here if you're interested): For a given set of points P, of which we have two copies - sorted in X and Y direction - Px and Py, the algorithm can be given as
closestPair(Px,Py):
- Divide points into left half - Q, and right half - R, and form sorted copies of both halves along x and y directions - Qx,Qy,Rx,Ry
- Let closestPair(Qx,Qy) be points p1 and q1
- Let closestPair(Rx,Ry) be p2,q2
- Let delta be minimum of dist(p1,q1) and dist(p2,q2)
- This is the unfortunate case, let p3,q3 be the closestSplitPair(Px,Py,delta)
- Return the best result
Now, the clarification that I want is related to step 5. I should say this beforehand, that what I'm suggesting, is barely any improvement at all, but if you're still interested, read ahead.
Prof R says that since the points are already sorted in X and Y directions, to find the best pair in step 5, we need to iterate over points in the strip of width 2*delta, starting from bottom to up, and in the inner loop we need only 7 comparisions. Can this be bettered to just one?
How I think is possible seemed a little difficult to explain in plain text, so I drew a diagram and wrote it on paper and uploaded it here:
Since no one else came up with is, I'm pretty sure there's some error in my line of thought. But I have literally been thinking about this for HOURS now, and I just HAD to post this. It's all that is in my head.
Can someone point out where I'm going wrong?
© Programmers or respective owner