I am trying to understand how to go from n log^2 n time to n log n time for the closet pair algorithm. I get the below part (from http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html)
- Divide the set into two equal sized parts by the line l, and recursively compute the minimal distance in each part.
- Let d be the minimal of the two minimal distances.
- Eliminate points that lie farther than d apart from l
- Sort the remaining points according to their y-coordinates
- Scan the remaining points in the y order and compute the distances of each point to its five neighbors.
- If any of these distances is less than d then update d.
Step 4 is a sort that takes O(n log n) time, which dominates all other steps and this is the one that needs to be reduced to O(n) in order for the overall algorithm to achieve O(n log n) time. And this is the part I am having a hard time understanding. The author proposes
Step 1: Divide the set into..., and recursively compute the distance in each part, returning the points in each set in sorted order by y-coordinate. Step 4: Merge the two sorted lists into one sorted list in O(n) time.
You still have to sort the points by the y-coordinate in the recursive step, which takes O(n log n) time. How can we avoid this? The merging is O(n), but we still have to sort somewhere.