====== Chapter 5.4: Finding the Closest Pair of Points ======
Given //n// points on a plane, our goal is to find the pair that is closest together. Comparing every possible pairing would take O(n^2) time. However, it is possible to do this in O(nlogn) time.

===== The Algorithm =====
We will denote the set of points by //P={p_1,..., p_n}//, where //p_i// has coordinates //(x_i,y_i)//; and for two points //p_i,p_j//, //d(p_i,p_j)// to denote the Euclidean distance between them. We will also assume that all points have distinct coordinates. Our goal is to find a pair of coordinates //p_i// and //p_j// such that //d(p_i,p_j)// is minimized. We will approach this problem in a way that is similar to Mergesort: we will find the closest pair among the points in the left half of //P// and the closest pair among the right half of //P//.

Closest-Pair(P):
  * construct P_x and P_y (sorted lists by x and y coordinate, respectively)
  * (p_0*,p_1*) = Closest-Pair-Rec(P_x,P_y)

Closest-Pair-Rec(P_x,P_y):
  * If |P|< = 3 then find closest pair by measuring all pairwise distances
  * Construct Q_x,Q_y,R_x,R_y
  * (q_0*,q_1*) = Closest-Pair-Rec(Q_x,Q_y)
  * (r_0*,r_1*) = Closest-Pair-Rec(R_x,R_y)
  * δ=min(d(q_0*,q_1*), d(r_0*,r_1*))
  * x*=maximum x-coordinate of a point in set Q
  * L={(x,y): x=x*}
  * S= points in P within distance δ of L
  * Construct S_y
  * for each point s in S_y, compute distance from s to each of the next 15 points in S_y
  * //Let s,s' be pair achieving minimum of these distances//
  * If d(s,s')<δ then return (s,s')
  * else if: if d(q_0*,q_1*) < d(r_0*,r_1*) then return (q_0*,q_1*)
  * else: return (r_0*,r_1*)

this runs in O(nlogn)

I would rate this section a 6. The algorithm made more sense in class. I was really confused by all of the additional variables in this algorithm.