5. This problem addresses part of the analysis of the 2D Closest-Pair algorithm from class. The analysis of the algorithm considers a 28-by-8 rectangular strip, split by the median line into two d-by-d square areas. All points that the algorithm placed in the "left" subset (which must lie to the left of, or on, the median line) are at distance at least 8 from each other, and similarly, all points placed in the "right" subset (which must lie to the right of, or on, the median line) are at distance at least d from each other. In particular, to show that the algorithm performs any better (asymptotically) than the nave algorithm (comparing every pair of points in the plane using O(n) comparisons), we show that the "combination" portion of this algorithm only needs a constant number of comparisons per point in the bounding rectangle used in the analysis of the algorithm. PL PR 1 8 Figure 1: The 28-by- rectangle used in the analysis and points within & of the median line (a) Prove that the left square area can contain at most 4 points from the left subset, and similarly that the right square area can contain at most 4 points from the right subset. Hint: partition each square area into four congruent square sub-areas, and show that each sub-area can have at most one point from the relevant subset. (b) Use the previous part to argue why it suffices for the "conquer" part of the Closest- Pair algorithm to check only the subsequent 8 points in the array for each point in the y-sorted array of points within & of the median line. (Note: the value 8 here is not optimal, but for the asymptotics we only need a constant.)