Friday, January 23, 2015

Finding closet pair


Assuming multiple points in a 2D dimension, what is the pair of points with closest distance

Naive brute-force solution

Double loop through all points in the scope and find the closest pair will cost O(n^2). However, we can improve and reduce the operational time to O(nlogn) as a smart algorithm demonstrates below.

O(nlogn) for closest pair

note that this is not the details for this algorithm, only the essentials/magics used in it.

  1. Sort points by x-cooridnate and y-cooridnate respectively and store in two arrays => Px, Py. This step will have running time of O(nlogn) with mergesort, which we discussed in one  previous blog, or quick sort.
  2. utilizing "divide and conquer paradigm" and construct recursive function as below:
  3. split points by half => find the closest pair in left half => find the closest pair in right half => find the closest pair with 1 point in left half and 1 point in right half. here the last step, i.e.split_counting, is the difficulty.
  4. By first observing the split_counting step, it has running time of O(n^2), because all points are possible candidates. however, by proof we see that only the subsequent 7 points in Py array can make a closest pair, which is:
    1. for i = 0, i in Py
      1. for j = i + 1, j in [i ... i + 7]
        1. count_cloest_pair(Pi, Pj)
  5. in the nested loop above, it has running time of O(n) only! this is the beauty of this algorithm.

for this algorithm details and the mathematics proof, please google "closest pair algorithm".

No comments:

Post a Comment