title: A divide-and-conquer algorithm for counting dominating points?
body: <p>Let's say that a point at coordinate (x1,y1) <em>dominates</em> another point (x2,y2) if x1 &le; x2 and y1 &le; y2;</p>
  
  <p>I have a set of points (x1,y1) , ....(xn,yn) and I want to find the total number of dominating pairs.  I can do this using brute force by comparing all points against one another, but this takes time O(n<sup>2</sup>). Instead, I'd like to use a divide-and-conquer approach to solve this in time O(n log n).</p>
  
  <p>Right now, I have the following algorithm:</p>
  
  <ul>
  <li><p>Draw a vertical line dividing the set of points points into two equal subsets of P<sub>left</sub> and P<sub>right</sub>. As a base case, if there are just two points left, I can compare them directly.</p></li>
  <li><p>Recursively count the number of dominating pairs in P<sub>left</sub> and P<sub>right</sub></p></li>
  <li><p>Some conquer step?</p></li>
  </ul>
  
  <p>The problem is that I can't see what the "conquer" step should be here. I want to count how many dominating pairs there are that cross from P<sub>left</sub> into P<sub>right</sub>, but I don't know how to do that without comparing all the points in both parts, which would take time O(n<sup>2</sup>).</p>
  
  <p>Can anyone give me a hint about how to do the conquer step?
  <img src="https://i.stack.imgur.com/Mnf3Q.png" alt="this is my example"></p>
  
  <p>so the 2 halves of y coordinates are : {1,3,4,5,5} and {5,8,9,10,12}</p>
  
  <p>i draw the division line. </p>