2: 3: 4: 6: (30 pts.) The loneliest point Given a set of n points in the plane, let the loneliest point be the point which is furthest away from all other points. There could be multiple loneliest points if there are ties; e.g. in a set of two points both are loneliest. Suppose we tried to find a loneliest point using divide-and-conquer in the following way: 1: function FIND-LONELIEST(a list P of n points) Sort P in order of increasing x coordinate (say breaking ties with the y coordinate) p,dp + HELPER(P) return p 5: function HELPER(P[O...n - 1]) # Return a loneliest point in P and its distance to the nearest point. if n=1 then return (P[O],-) [n/2] left points - P[O..m - 1] right-points + P[m..n - 1] l,de + HELPER(left points) # Recursively find loneliest points in left and right halves r,dr + HELPER(right-points) de + min(de, minperight-points (l,p)) # Check distance from l to all points on right dr + min(d,, min peleff points d(r, p)) # Check distance from r to all points on left if ded, then return (,de) # Return whichever of lor r is lonelier else return (r, dr) 7: m 8: 9: 10: 11: 12: 13: 14: 15: 16: (a) What is the asymptotic runtime of this algorithm? Justify your answer, explaining how long each of the steps of the algorithm takes. (b) Unfortunately, this algorithm doesn't work! Explain the reason why the algorithm can go wrong, and give an example set of points where it returns a non-loneliest point. (If you're interested, you can try to fix the algorithm! You can use an approach similar to the closest-pair algorithm we saw in class.)