In this problem we will develop a divide-and-conquer algorithm for the following geometric task. Closest PaIR Input: A set of points in the plane, {p1=(x1,y1),p2=(x2,y2),,pn=(xn,yn)} Output: The closest pair of points: that is, the pair pi=pj for which the distance between pi and pj, that is, (xixj)2+(yiyj)2, is minimized. For simplicity, assume that n is a power of two, and that all the x-coordinates xi are distinct, as are the y-coordinates. Here's a high-level overview of the algorithm: - Find a value x for which exactly half the points have xix. On this basis, split the points into two groups, L and R. - Recursively find the closest pair in L and in R. Say these pairs are pL,qLL and pR,qRR, with distances dL and dR respectively. Let d be the smaller of these two distances. - It remains to be seen whether there is a point in L and a point in R that are less than distance d apart from each other. To this end, discard all points with xix+d and sort the remaining points by y-coordinate. - Now, go through this sorted list, and for each point, compute its distance to the seven subsequent points in the list. Let pM,qM be the closest pair found in this way. - The answer is one of the three pairs {pL,qL},{pR,qR},{pM,qM}, whichever is closest. (a) In order to prove the correctness of this algorithm, start by showing the following property: any square of size dd in the plane contains at most four points of L. (b) Now show that the algorithm is correct. The only case which needs careful consideration is when the closest pair is split between L and R. (c) Write down the pseudocode for the algorithm, and show that its running time is given by the recurrence: T(n)=2T(n/2)+O(nlogn). Show that the solution to this recurrence is O(nlog2n). (d) Can you bring the running time down to O(nlogn)