title: Closest pair of points Planar case
body: <p>I am looking at the wikipedia entry for how to solve this. It lists five steps</p>
  
  <p>1.Sort points along the x-coordinate</p>
  
  <p>2.Split the set of points into two equal-sized subsets by a vertical line x = xmid</p>
  
  <p>3.Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances dLmin and dRmin respectively.</p>
  
  <p>4.Find the minimal distance dLRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.</p>
  
  <p>5.The final answer is the minimum among dLmin, dRmin, and dLRmin.</p>
  
  <p>The fourth step I am having trouble understanding. How do I choose what point to the left of the line to compare to a point right of the line. I know I am not supposed to compare all points, but I am unclear about how to choose points to compare. Please do not send me a link, I have searched, gone to numerous links, and have not found an explanation that helps me understand step 4.</p>
  
  <p>Thanks</p>
  
  <p>Aaron</p>