Search algorithm for non-dominated pairs

Question

The data are pairs of integers (a1,b1),...,(an,bn) . The pair i dominates the pair j if ai < aj and bi < bj . What is an algorithm for quickly determining a list of pairs in which no other pair dominates?

We can check all the pairs, and for each pair, check if any other pair prevails by passing all the pairs again. This algorithm is of order n^2 . Is there an algorithm of order n or n log n ?

Answer 1

We can find non-dominated pairs at O(n log n) time.

Sort the pairs, decreasing the order of a_i , and then iterate over the pairs. In addition, keep track of the maximum value of b indicated so far, b_max . At each step, if the next (a_i,b_i) pair has a value b greater than b_max , add it to the list of answers and update b_max . The final list of answers will be non-dominated pairs.

Correctness: a pair dominates if and only if some pair has a larger a and more b . When we consider a pair, we compare its value b exactly to the maximum value of b among pairs with large a s, so we add a pair to the list if and only if it does not dominate.

Runtime: sorting pairs by value takes O(n log n) . Iteration takes O(n) time, so the total execution time is O(n log n) .

Answer 2

if I understand him correctly, a non-dominated pair is such that either a or b is greater than or equal to the maximum value for a and b, respectively.

Therefore, you just need to find such maximum values ​​(a for the O (n) cycle) for a and b, and then run another cycle to find a pair that satisfies the above condition. in general, the time complexity is O (n).

A small example in Java that returns an ArrayList of indices for non-dominant pairs:

  ArrayList<Integer>findUndominatedPairIndexes(int[][]arrayOfPairs) { ArrayList<Integer>result=new ArrayList<Integer>(); int maxX=Integer.MIN_VALUE; int maxY=Integer.MIN_VALUE; int i=arrayOfPairs.length; /** * get the max value */ for(;--i>=0;) { int x=arrayOfPairs[i][0]; int y=arrayOfPairs[i][1]; if (x>maxX) { maxX=x; } if (y>maxY) { maxY=y; } } for(i=arrayOfPairs.length;--i>=0;) { int[] pair=arrayOfPairs[i]; if (pair[0]>=maxX||pair[1]>=maxY) { result.add(new Integer(i)); } } return result; }