We now describe another problem that can be solved by an algorithm in the style we have been discussing; but finding the right way to “merge” the solutions to the two sub problems it generates requires a bit of ingenuity. The Problem. Given n points in a plane, find the pair that is closest together. This problem was considered by M.I Shamos and D.Hoey in the early 70s to work out efficient algorithms for basic computational geometry. It is hard to find an efficient algorithm for this problem. They finally discovered an algorithm that runs in O(n log n) time. We shall see further in Ch 13 that this could still be improved to O(n) time. Designing the Algorithm. Our goal is to find a pair of points that minimizes the standard Euclidean distance between them. Note that no two points have the same coordinates. If we were finding the shortest distance between any points on aline, we would have to first sort them in O(n log n) time, then walk through them and compute the distance between each point and the point after it and determine the least. In 2D, we shall have to find the closest pair among the points in the left half of P and the closest pair among the points in the right half of P; and then use this information to get the overall solution, and this would take us O(n log n) time. What about the distances between points across the halves?? Are there any distances across both halves that is the least distance overall. If not then the least distances is either in the right or left halves. Another claim says that if there are two points whose distance is less than the previously found least distance, then these two points are within 15 positions of each other in the Sorted list. The value 15 is just an absolute constant but it can be reduced. We can now conclude the algorithm by saying, for each point we compute its distance to each of the next 15 points in S. A summary of the algorithm is on page 230. Analyzing the Algorithm: The algorithm correctly outputs a closest pair of points in P and the running time of this algorithm is O(n log n). The proof for both of these conclusion are on page 231.

This section was “mind-blowing” and I give it a 7.5/10 scale.