You are known as one of the most distinguished astronomers in the country, capturing images sky for decades on end. In the mail, arrives an invite to an art exhibition in New York. You've been invited to star in an exhibition! However, you are only allowed to submit one photo. What to show? You could show a photo of a single planet, but that's been done before. Then, you have an idea! What about two planets that are close to each other? You quickly realise that in order to have the highest resolution photo possible, you will need to find the closest pair of planets in your collection. The problem is, you've captured billions of planets over the years, and don't have time to compare every pair of planets! Lucky for you, you remember that lying around are the (x, y) co-ordinates for the positions of each and every planet in the night sky. You've heard talk around the town, that a technique called divide and conquer might be able to help!
We need to design an algorithm that solves the following task T: given a set S of size n containing point P(x, y), where x, y e R+, representing the position of each planet in two dimensional space in the night sky, find the pair of planets {P_1, P_2}, where {P_1, P_2} is a set of two points P(x, y), that are the closest to each other.
Note, there may be more than 1 pair of planets that are both the closest and equidistant from each other. Therefore, you should return a set of pairs {P_1, P_2}.