Finding the dominating pairs in a set of coordinates in O(nlgn) [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

Improve this question

a coordinate a(xa,ya) dominates b(xb,yb) if ( xa>=xb and ya>=yb) how can I find all pairs in a set of coordi开发者_高级运维nates in nlgn using divide and conquer?

edit:the number of pairs instead.

---

Do a quick sort where your comparison is first to sort by X then Y ( so you'd get something like 5,3 5,2 4,7 4,2 etc. Quicksort is nlogn

Then just iterate from the highest point down doing your compare. That would be at most O(n). You end up with O(n) + O(nlogn) => O(nlogn)

Quicksort uses divide and conquer - it divides on the pivot.

EDIT:

Another thing I considered. You can walk the entire set and put all the points that are dominated in the X coordinate by your point in a set. Then, walk that smaller subset and filter out the ones that are also dominated by your Y. This is just two walks, for O(n) performance.

---

Roughly speaking, any given vector (xa,ya) will dominate or be dominated by about half of the other vectors (ya,yb), because among the four cases for {xa <=> ya, xb <=>yb}, two are cases of dominance.

So we expect the solution to your problem to comprise about n*(n/2) pairs of vectors. The algorithm can't be cheaper than its solution, so n*ln(n) is not going to work.

---

lets say you have the points such that

a1 > a2 > a3 ... > an-1 > an d (read > as dominates) n is proporional to the number of points (N) in all situations.

the number of pairs itself is greater than nlogn (such as (A[1],A[2..n]) (A2], A[3..n]) ..A[n=1], A[n]) I think that is n (n-1) / 2.

so N logN doesn't seem to be possible

---

Assuming that you only need to count the number of pairs, you can take the sweeping approach:

1) Sort the points according to their X values

2) Collect the points into a search tree.

Here we use a balanced tree based on the Y values of the points. The tree should have a counter per internal node, indicating the number of items in the subtree rooted by it. These counters can be maintained without any impact on the time complexity of the tree operations. The usage of counters allows querying the number of items lower than a given value V, in logarithmic time.

More details on (2): we scan the points obtained in step (1) from left to right. For each point P traversed, we add P to the tree, and then compute the number of items with Y < P.Y. This number is added to the global count which is returned at the end.

Step (1) runs in N*Log(N) time, and step (2) performs N iterations of two Log(N) operations, therefore it has the same complexity.