What is wrong with my logic for the divide and conquer algorithm for Closest pair problem?
- by Programming Noob
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?
