Closest Pair Of Points

#+-------------------------
# Author: Nehal J Wani
# Date: Aug 20, 2012
# Algorithms, Closest Pair
#+-------------------------

#Calculate the eucledian distance
def eDist(pair):
    return (pair[0][0]-pair[1][0])**2+(pair[0][1]-pair[1][1])**2

#Sort input according to x-coordinate and y-coordinate
def closestPair(P):
    Px=sorted(P,key=lambda x:x[0])
    Py=sorted(P,key=lambda y:y[1])
    return closestPairRec(Px,Py)

#Applying brute force for less than three points
def pairByBruteForce(P):
    bestPair=(P[0],P[1])
    bestDist=eDist(bestPair)
    for i in range(len(P)):
        for j in range(i+1,len(P)):
            dist=eDist((P[i],P[j]))
            if dist<bestDist:
                bestDist=dist
                bestPair=(P[i],P[j])
    return bestPair

#Divide & Conquer
def closestPairRec(Px,Py):
    n=len(Px)

    #Base case
    if len(Px)<=3:
        return pairByBruteForce(Px)

    #Dividing input into halves
    Qx=Px[:n/2]
    Qy=Py[:n/2]
    Rx=Px[n/2:]
    Ry=Py[n/2:]

    #Closest points in left half and right half
    (q0,q1)=closestPairRec(Qx,Qy)
    (r0,r1)=closestPairRec(Rx,Ry)

    dQ=eDist((q0,q1))
    dR=eDist((r0,r1))

    if dQ>dR:
        bestPair=(r0,r1)
        delta=dR
    else:
        bestPair=(q0,q1)
        delta=dQ

    #Separator line
    x_=Qx[-1][0]

    #Split-point 'unlucky' case
    S=filter(lambda x: abs(x[0]-x_)<delta,Qx+Rx)
    Sy=sorted(S,key=lambda y:y[1])

    if len(Sy)<=7 and len(Sy)>1:
        splitPair=pairByBruteForce(Sy)
        if eDist(splitPair)<delta:
            bestPair=splitPair

    #Find the points with distance < delta
    for i in range(len(Sy)-7):
        for j in range(i+1,i+8):
            dist=eDist((Sy[i],Sy[j]))
            if dist<delta:
                delta=dist
                bestPair=(Sy[i],Sy[j])
    return bestPair


P=[(0,0),(7,6),(2,20),(12,5),(16,16),(5,8),(19,7),(14,22),(8,19),(7,29),(10,11),(1,13)]
print closestPair(P)