Closest Pair

Input:

• A set of points (x,y) we'll call P; $S = {P_1, P_2, P_3 ... P_n}$

Output:

• Return the two points that are closest to each other.

• We define closest by euclidean distance

  • $min(d = \sqrt{(x_2-x_1)^2 + (y_2 - y_1)^2})$

Assumptions:

• No duplicate points

Naive Approach

• $O(n^2)$

• Double for loop, calculate the distance between every possible point, maintains the minimum along the way.

• It is worth noting that the upper bound is n^2, but really we are calculating nC2 combination pairs. For a visual of this, see Combinatorics chapter in ADT gitbook.

1-D Solution

• While a brute force solution still exists, we can do better

• If we limited our points in d-1 we can solve this in nlogn by:

• Sorting -> nlogn

• Scanning through it again, and then finding the minimum distance between two pairs of points. -> O(N)

2-D Solution

• Motivated by our 1-d case, we may want to try and sort both the x and y coordinate sets by their dimension and then go through there.

  • But, we can easily derive an example where although 2 coordinates appear very per 1 axis, they are in reality a lot further in the other axis.

  • We find that our 1-dimensional approach will not work.

Divide and Conquer

• Split the pairs of points vertically, such that there are the same amount of points on each side (if odd, differ by 1).

  • We accomplish this by sorting the points respectfully by x-cord, and y-cord - and finding the median.

• Solve the closest pairs of points on 1st half, and then in the 2nd half.

  • At this point if we calculate both sides, then it would take each $(n/2)^2$ for each. Which is still of order $n^2$. We have also yet to consider the closest pair of points that are considered between these two discrete sets.

Achieving nlogn:

• The idea is to continue dividing our data in half until we reach the point where we have 2 or 3 points. Our return condition would be to then use brute force to find the closest pair of points for that call.

• We do the same thing with the right hand side.

• Then we find the minimum of the two sides, lets call this min_d

• Finally, we only consider points from the vertical line + mid_d distance away. We can be assured that points further than mid_d from the median line are not the closest.

  • Here we find the distance between crossing points.

http://www.geeksforgeeks.org/closest-pair-of-points-onlogn-implementation/

http://www.yovisto.com/video/9661

Simplified

1. Sort points by x-cord <- Px

2. Sort points by y-cord <- Py

3. Split Px in half (median; size/2)