this algorithm runs in O(n log n) time. Let’s consider two variations on this problem:
(a) First consider the problem of searching for the closest pair of points in 3-dimensional space. Show
how you could extend the single plane closest pairs algorithm to find closest pairs in 3D space. Your
solution should still achieve O(n log n) run time.
(b) Now consider the problem of searching for the closest pair of points on the surface of a sphere
(distances measured by the shortest path across the surface). Explain how your algorithm from
part a can be used to find the closest pair of points on the sphere as well.
(c) Finally, one way to approximate the surface of a sphere is to take a plane and "wrap" at the edges,
so a point at x coordinate 0 and y coordinate MAX is the same as x coordinate 0 and y coordinate
MIN. Similarly, the left and right edges of the plane wrap around. Show how you could extend the
single plane closest pairs algorithm to find closest pairs in this space.