A divide-and-conquer algorithm for counting dominating points?

Question

Let's say that a point at coordinate (x1,y1) dominates another point (x2,y2) if x1 ≤ x2 and y1 ≤ y2;

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²). Instead, I'd like to use a divide-and-conquer approach to solve this in time O(n log n).

Right now, I have the following algorithm:

• Draw a vertical line dividing the set of points points into two equal subsets of P_left and P_right. As a base case, if there are just two points left, I can compare them directly.

• Recursively count the number of dominating pairs in P_left and P_right

• Some conquer step?

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_left into P_right, but I don't know how to do that without comparing all the points in both parts, which would take time O(n²).

Can anyone give me a hint about how to do the conquer step?

so the 2 halves of y coordinates are : {1,3,4,5,5} and {5,8,9,10,12}

i draw the division line.

Answer 1

Suppose you sort the points in both halves separately in ascending order by their y coordinates. Now, look at the lowest y-valued point in both halves. If the lowest point on the left has a lower y value than the lowest point on the right, then that point is dominated by all points on the right. Otherwise, the bottom point on the right doesn't dominate anything on the left.

In either case, you can remove one point from one of the two halves and repeat the process with the remaining sorted lists. This does O(1) work per point, so if there are n total points, this does O(n) work (after sorting) to count the number of dominating pairs across the two halves. If you've seen it before, this is similar to the algorithm for counting inversions in an array).

Factoring in the time required to sort the points (O(n log n)), this conquer step takes O(n log n) time, giving the recurrence

T(n) = 2T(n / 2) + O(n log n)

This solves to O(n log² n) according to the Master Theorem.

However, you can speed this up. Suppose that before you start the divide amd conquer step that you presort the points by their y coordinates, doing one pass of O(n log n) work. Using tricks similar to the closest pair of points problem, you can then get the points in each half sorted in O(n) time on each subproblem of size n (see the discussion at this bottom of this page) for details). That changes the recurrence to

T(n) = 2T(n / 2) + O(n)

Which solves to O(n log n), as required.

Hope this helps!