Q4: Divide and conquer for closest pair

Given a set of points in a plane, $p = \left\{(x_0,y_0),(x_1,y_1),\ldots,(x_{n-1},y_{n-1})\right\}$ , consider the problem of determining the closest pair of points; i.e., pairs $p_i$ and $p_j$ such that the distance between them $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$ is minimized.

Clearly the naive idea of computing the $n(n+1)/2$ distances and finding the minimum gives an $O(n^2)$ algorithm. Here is an improvement using divide and conquer.

1. Find a value $x$ such that half the points have $x_i <= x$ and half have $x_i > x$ (roughly; you may sort the set on their $x$ coordinates to do this). On this basis split in to two groups $L$ and $R$ .
2. Recursively compute the closest pair in $L$ and in $R$ . Let these pairs be $p_L,q_L \in L$ and $p_R,q_R \in R$ , with distances $d_L$ and $d_R$ respectively. Let the smaller of these distances be $d$ .
3. It remains to be seen if there is a point in $L$ and a point in $R$ that are less than $d$ distance apart from each other. To this end, discard all points with $x_i < x - d$ and $x_i > x+d$ and sort the remaining points in the central band by their $y$ coordinates.
4. Now, go through this sorted list, and for each point, compare its distance to the seven subsequent points in the list (why?). Let $p_M,q_M$ be the closest pair found this way.
5. The answer is one of the three pairs $\{p_L,q_L\}$ , $\{p_R,q_R\}$ and $\{p_M,q_M\}$ , whichever is closest.

How efficient is this algorithm? Write an imperative program based on the above idea.

You may write the program in any language of your choice. However it may be simplest to complete this Python program template.