RosettaCodeData/Task/Closest-pair-problem/00-TASK.txt

;Task:
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 &nbsp; O(n<sup>2</sup>) &nbsp; algorithm &nbsp; (which we can call ''brute-force algorithm''); &nbsp; the pseudo-code (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, &nbsp; as explained also at &nbsp; [[wp:Closest pair of points problem#Planar_case|Wikipedia's Closest pair of points problem]], &nbsp; which is &nbsp; O(''n'' log ''n''); &nbsp; a pseudo-code 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:
* &nbsp; [[wp:Closest pair of points problem|Closest pair of points problem]]
* &nbsp; [http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html Closest Pair (McGill)]
* &nbsp; [http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf Closest Pair (UCSB)]
* &nbsp; [http://classes.cec.wustl.edu/~cse241/handouts/closestpair.pdf Closest pair (WUStL)]
* &nbsp; [http://www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt Closest pair (IUPUI)] 
<br><br>