I am currently assigned to create a c++ program to find the closest pair of points in a (x,y) coordinate system. However, I am having a lot of trouble trying to understand one thing.
Every tutorial/guide that I have read about the closest pair problem it tells me to sort the set of points by there Y coordinates, but I don't see what the point of this is? Can someone explain to me why we sort it by Y coordinates and what is the use of it? I understand that we sort the points by X in order to get L and X*, but I just don't understand why we have to sort the points by Y coordinates as well.
You don't, but then your running time is not improved over O(n2). The whole point is to compute as little as possible -- by examining as few points as possible, ignoring those you know will not be part of the answer. Do that by sorting Y.
Here's a pretty good explanation I just googled: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html