Solve the Closest Pair Algorithm with recursion(Divide and Conquer) -

i understand how solve infamous "closest pair problem" using brute force, simple algorithm in o(n^2) running time might work recursively? problem is

given set of n points, write code find closest pair of points

what simple recursive function can used solve problem?

here's test problem, first number number of points , following lines contain points themselves:

6 0 5 1 13 5 9 1 8 3 10 6 10 

this code finds nearest pair of points of using divide , conquer, , runs in o(n^2) time. efficient algorithm (which you're trying understand) replaces part starts "for left in pl": instead of comparing every pair of points left , right sides, compares @ 6 points right side every point on left.

the closest function here returns distance squared of nearest pair pair of points. that's convenient taking mins.

import itertools  def dist2(a, b):     return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2  def closest(a):     if len(a) <= 3:         return min((dist2(a, b), (a, b)) a, b in itertools.combinations(a, 2))     pl = a[:len(a)//2]     pr = a[len(a)//2:]     result = min(closest(pl), closest(pr))     left in pl:         right in pr:             result = min(result, (dist2(left, right), (left, right)))     return result  test = [map(float, x.split(' ')) x in '0 5,1 13,5 9,1 8,3 10,6 10'.split(',')] print closest(test)