title: Closest Pair Implemetation Python
body: <p>I am trying to implement the closest pair problem in Python using divide and conquer, everything seems to work fine except that in some input cases, there is a wrong answer. My code is as follows:</p>
  
  <pre><code>def closestSplitPair(Px,Py,d):
      X = Px[len(Px)-1][0]
      Sy = [item for item in Py if item[0]&gt;=X-d and item[0]&lt;=X+d]
      best,p3,q3 = d,None,None
      for i in xrange(0,len(Sy)-2):
          for j in xrange(1,min(7,len(Sy)-1-i)):
              if dist(Sy[i],Sy[i+j]) &lt; best:
                  best = (Sy[i],Sy[i+j])
                  p3,q3 = Sy[i],Sy[i+j]
      return (p3,q3,best)
  </code></pre>
  
  <p>I am calling the above function through a recursive function which is as follows:</p>
  
  <pre><code>def closestPair(Px,Py): """Px and Py are input arrays sorted according to
  their x and y coordinates respectively"""
      if len(Px) &lt;= 3:
          return min_dist(Px)
      else:
          mid = len(Px)/2
          Qx = Px[:mid] ### x-sorted left side of P
          Qy = Py[:mid] ### y-sorted left side of P
          Rx = Px[mid:] ### x-sorted right side of P
          Ry = Py[mid:] ### y-sorted right side of P
          (p1,q1,d1) = closestPair(Qx,Qy)
          (p2,q2,d2) = closestPair(Rx,Ry)
          d = min(d1,d2)
          (p3,q3,d3) = closestSplitPair(Px,Py,d)
          return min((p1,q1,d1),(p2,q2,d2),(p3,q3,d3),key=lambda tup: tup[2])
  </code></pre>
  
  <p>where <code>min_dist(P)</code> is the brute force implementation of the closest pair algorithm for a list P having 3 or less elements and returns a tuple containing the pair of closest points and their distance.</p>
  
  <p>If my input is <code>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)]</code>, then my output is <code>((5,8),(7,6),2.8284271)</code> which is the correct output. But when my input is <code>P = [(94, 5), (96, -79), (20, 73), (8, -50), (78, 2), (100, 63), (-14, -69), (99, -8), (-11, -7), (-78, -46)]</code> the output I get is <code>((78, 2), (94, 5), 16.278820596099706)</code> whereas the correct output should be <code>((94, 5), (99, -8), 13.92838827718412)</code></p>