{{Wikipedia|Closest pair of points problem}}
The aim of this task is to provide a function to find the closest two points among a set of given points in two dimensions, i.e. to solve the [[wp:Closest pair of points problem|Closest pair of points problem]] in the ''planar'' case.

The straightforward solution is a O(n<sup>2</sup>) algorithm (which we can call ''brute-force algorithm''); the pseudocode (using indexes) could be simply:

 '''bruteForceClosestPair''' of P(1), P(2), ... P(N)
 '''if''' N &lt; 2 '''then'''
   '''return''' â
 '''else'''
   minDistance â |P(1) - P(2)|
   minPoints â { P(1), P(2) }
   '''foreach''' i â [1, N-1]
     '''foreach''' j â [i+1, N]
       '''if''' |P(i) - P(j)| < minDistance '''then'''
         minDistance â |P(i) - P(j)|
         minPoints â { P(i), P(j) }
       '''endif'''
     '''endfor'''
   '''endfor'''
   '''return''' minDistance, minPoints
  '''endif'''

A better algorithm is based on the recursive divide&amp;conquer approach, as explained also at [[wp:Closest pair of points problem#Planar_case|Wikipedia]], which is O(''n'' log ''n''); a pseudocode could be:

 '''closestPair''' of (xP, yP)
                where xP is P(1) .. P(N) sorted by x coordinate, and
                      yP is P(1) .. P(N) sorted by y coordinate (ascending order)
 '''if''' N â¤ 3 '''then'''
   '''return''' closest points of xP using brute-force algorithm
 '''else'''
   xL â points of xP from 1 to âN/2â
   xR â points of xP from âN/2â+1 to N
   xm â xP(âN/2â)<sub>x</sub>
   yL â { p â yP : p<sub>x</sub> â¤ xm }
   yR â { p â yP : p<sub>x</sub> &gt; xm }
   (dL, pairL) â ''closestPair'' of (xL, yL)
   (dR, pairR) â ''closestPair'' of (xR, yR)
   (dmin, pairMin) â (dR, pairR)
   '''if''' dL &lt; dR '''then'''
     (dmin, pairMin) â (dL, pairL)
   '''endif'''
   yS â { p â yP : |xm - p<sub>x</sub>| &lt; dmin }
   nS â number of points in yS
   (closest, closestPair) â (dmin, pairMin)
   '''for''' i '''from''' 1 '''to''' nS - 1
     k â i + 1
     '''while''' k â¤ nS '''and''' yS(k)<sub>y</sub> - yS(i)<sub>y</sub> &lt; dmin
       '''if''' |yS(k) - yS(i)| &lt; closest '''then'''
         (closest, closestPair) â (|yS(k) - yS(i)|, {yS(k), yS(i)})
       '''endif'''
       k â k + 1
     '''endwhile'''
   '''endfor'''
   '''return''' closest, closestPair
 '''endif'''


'''References and further readings'''
* [[wp:Closest pair of points problem|Closest pair of points problem]]
* [http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html Closest Pair (McGill)]
* [http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf Closest Pair (UCSB)]
* [http://classes.cec.wustl.edu/~cse241/handouts/closestpair.pdf Closest pair (WUStL)]
* [http://www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt Closest pair (IUPUI)]
