$1.$ Ecosystem Restoration in Algorithmia A wildlife conservation team in the land of Algorithmia is working on an ecosystem restoration project in a large forest. They have identified n small water bodies $($ponds$)$ at locations $($x$1,$ y$1),...,($xn$,$ yn$).$ To create larger habitats for aquatic life, they plan to merge the two closest ponds, reducing the number of ponds in the forest to n $1.$ Since the researchers will merge the ponds by digging around a grid of trees, to find the two closest you will use Manhattan distance, aka d$(($xi$,$ yi$),($xj $,$ yj$))=|$xi $$ xj $|+|$yi $$ yj $|.$ Assumption: the coordinates are integers, but possibly large ones. You cannot use Radix$-$ Sort for this problem. $($a$)$ Design a deterministic O$($n log$^2($n$))$ time algorithm for finding the two closest ponds. $[$We are expecting: English description, pseudocode, and running time analysis. No proof of correctness required!$]$ Hint: A brute force algorithm that computes the distance between each pair of ponds takes O$($n$^2).$ Back in section $2$ when we tackled the Maximum Sum Subarray problem, we used a divideand$-$ conquer approach to optimize our brute force algorithm for that problem from O$($n$^2)$ to O$($n log n$).$ Would a similar approach help us here again? The following fact may be useful: Fact $1.$ There is some constant c $($aka c $=$ O$(1))$ such that in a $3$d $3$d square, there can be at most c ponds that are all distance at least d from each other. $($You can have a lot of fun trying to compute c$,$ but we advise that you do it only after finishing your homework!$)$