Division and conquest algorithm for counting dominant points?

Question

Say that a point in the coordinate (x1, y1) dominates another point (x2, y2) if x1 & le; x2 and y1? y2;

I have a set of points (x1, y1), .... (xn, yn), and I want to find the total number of dominant pairs. I can do this with brute force, comparing all the points against each other, but this takes O (n ² ) time. Instead, I would like to use the divide and conquer approach to solve this in time for O (n log n).

Now I have the following algorithm:

• Draw a vertical line dividing the set of point points into two equal subsets of P _left and P _right . As a base case, if only two points remain, I can compare them directly.

• Recursively count the number of dominant pairs in P _left and P _right

• Some conquest steps?

The problem is that I don’t see what the “win” step should take. I want to calculate how many dominant pairs there are, which crosses P _left in P _right , but I don’t know how to do this without comparing all the points in both parts that would take O (n ² ) time.

Can someone give me a hint on how to take a conqueror step?

so 2 half y coordinates: {1,3,4,5,5} and {5,8,9,10,12}

I draw a line of division.

Answer 1

Suppose you sort the points in both halves separately in ascending order by their y coordinates. Now consider the smallest y-digit point in both halves. If the lower point on the left has a lower y value than the lower point on the right, then all points on the right prevail at this point. Otherwise, the lower point on the right does not dominate anything on the left.

In any case, you can delete one point from one of the two halves and repeat the process with the remaining sorted lists. This means that O (1) works for each point, so if there are n common points, O (n) works (after sorting) to calculate the number of dominant pairs in two halves. If you've seen this before, it looks like an inverse counting algorithm in an array).

Factoring the time needed to sort the points (O (n log n)), this conquest step takes O (n log n) time, giving a repetition

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

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

However, you can speed it up. Suppose that before you start the divide amd conquer step, you must determine the points by their y coordinates by doing one O (n log n) pass. Using tricks similar to the closest pair of point problems, you can get points in each half, sorted by O (n) time for each subtask of size n (see the discussion in this lower part of this page ). This changes the repeat to

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

which decides O (n log n) if required.

Hope this helps!

Answer 2

So you have O (n ^ 2) just for division by subsets ...
My approach will be different.

• sort points by X ... O (n.log (n))
• now check y
  • but check only points with large X (if you sort them in ascending order, then with a large index)
• So now you have O (n.log (n) + (nn / 2))

You can also speed up the process by running separate tests X and Y, and then combine the result, which will lead to the output of O (n + 3.n.log (n))

• add an index attribute to your points
  • where index = 0xYYYYXXXXh is an unsigned integer
  • YYYY - index of a point in a Y-sorted array
  • XXXX is the index of a point in an X-sorted array
  • If you have more than 2 ^ 16 points, use more than the 32-bit data type.
• sort points in increasing X and set XXXX part of their index O1 (n.log (n))
• sort points in increasing Y and set YYYY part of their index O2 (n.log (n))
• sort points by ascending index O3 (n.log (n))
• now the point i dominates any point j if (i <j)
  • but if you need to create virtually all pairs for any point
  • which will take O4 (nn / 2), so this approach will save a little time
  • if you need only one pair for any point, then a simple loop will suffice O4 (n-1)
  • therefore, in this case, O (n-1 + 3.n.log (n)) → ~ O (n + 3.n.log (n))

hope this helps ... of course, if you are stuck with this unit because I don't have a better solution for you.

PS. for this you do not need additional recursion, but only 3-fold sorting and only one uint for any point, so the memory requirements are not so large and should even be faster than a recursive call for unit reduction in general

Answer 3

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

Follow these steps:

• Sort the list of points by y-coordinate (ascending), breaking bonds by x-coordinate (ascending).
• Go through the sorted list in reverse order to calculate the dominant points: if the current value of x-coordinates> = max x-coordinates is found then increase the result and update max.

This works because you know for sure that if all pairs with large y-coordinates have a smaller x coordinate than the current point, you have found dominant points. The sorting step makes it really effective.

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