We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array.
Algorithm to find closest pair of points(O(nlogn))
step 1) First we sort all points according to x coordinates.
step 2) Divide set all points in two set of half size.
step 3) Find the smallest distances in both subarrays
recursively.
step 4) find the minimum of two smallest distances say it d.
step 5) Create an array points[] that stores all points which are
at most d distance away from the middle line dividing the two
sets.
step 6) Find the smallest distance in points[].
step 7) Return the minimum of d and the smallest distance
calculated in above step 6.
Consider the algorithm to find the closest pair of points in the plane. Let's say you wanted to generalize the algorithm to find the two closest pairs of points in the plane given a set of (unsor...