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!

Answer 2

Well in this way you have O(n^2) just for division to subsets...
My approach would be different

1. sort points by X ... O(n.log(n))
2. now check for Y
   • but check only points with bigger X (if you sort them ascending then with larger index)
3. so now you have O(n.log(n)+(n.n/2))

You can also further speed things up by doing separate X and Y test and after that combine the result, that would leads O(n + 3.n.log(n))

1. add index attribute to your points
   • where index = 0xYYYYXXXXh is unsigned integer type
   • YYYY is index of point in Y-sorted array
   • XXXX is index of point in X-sorted array
   • if you have more than 2^16 points use bigger then 32-bit data-type.
2. sort points by ascending X and set XXXX part of their index O1(n.log(n))
3. sort points by ascending Y and set YYYY part of their index O2(n.log(n))
4. sort points by ascending index O3(n.log(n))
5. now point i dominates any point j if (i < j)
   • but if you need to create actually all the pairs for any point
   • that would take O4(n.n/2) so this approach will save not a bit of time
   • if you need just single pair for any point then simple loop will suffice O4(n-1)
   • so in this case O(n-1+3.n.log(n)) -> ~O(n+3.n.log(n))

hope it helped,... of course if you are stuck with that subdivision approach than i have no better solution for you.

PS. for this you do not need any additional recursion just 3x sorting and only one uint for any point so the memory requirements are not that big and even should be faster than recursive call to subdivision recursion in general

Answer 3

This algorithm runs in O(N*log(N)) where N is the size of the list of points and it uses O(1) extra space.

Perform the following steps:

1. Sort the list of points by y-coordinate (ascending order), break ties by x-coordinate (ascending order).
2. Go through the sorted list in reverse order to count the dominating points: if the current x-coordinate >= max x-coordinate value encountered so far then increment the result and update the max.

This works since you know for sure that if all pairs with a greater y-coordinates have a smaller x-coordinate than the current point you have found a dominating points. The sorting step makes it really efficient.

Here's the Python code:

def my_cmp(p1, p2):
    delta_y = p1[1] - p2[1]
    if delta_y != 0:
        return delta_y
    return p1[0] - p2[0]

def count_dom_points(points):
    points.sort(cmp = my_cmp)
    maxi = float('-inf')
    count = 0
    for x, y in reversed(points):
        if x >= maxi:
        count += 1
        maxi = x

    return count