THE LONELIEST POINT

------------------------------------

2: 3: 4: 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(0..n-1)) 6: # Return a loneliest point in P and its distance to the nearest point. if n=1 then return (P[O],-) m+ [n/2] left points + P[O..m 1] 10: right points + P[m..n 1] l,der HELPER(left-points) # Recursively find loneliest points in left and right halves 12: r,dr + HELPER(right-points) de + min(de, minperight-points d(l,p)) # Check distance from l to all points on right 14: dr + min(d,, minpeleft-points d(r, p)) # Check distance from r all points on left 15: if ded, then return (l,de) # Return whichever of l or r is lonelier 16: else return (r,dr) 7: 8: 9: 11: 13: (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.)