Finding Pareto optimal solution set in $O(n \log n)$ time

Question

http://cs-people.bu.edu/kvodski/teaching/spring10/lab7.html says:

For two points in 2-dimensional space, point ($x_i$, $y_i$) dominates ($x_j$, $y_j$) if $x_i > x_j$ and $y_i > y_j$. Given a set of points, a maxima is a point that is not dominated by any other point in the set. These points are sometimes called Pareto optimal (assuming larger values are better), and the set of maxima called the Pareto set. Given a set of $n$ 2-dimensional points, your task is to devise an $O(n \log n)$ algorithm to find the Pareto set.

Hint: draw a picture of what is going on, plot some points on paper and see which ones are Pareto optimal. Then figure out how you can find all of them efficiently. Your algorithm will need to start by sorting the points in one of the dimensions.

An $O(n^{2})$ algorithm is trivial, but an $O(n \log n)$ algorithm is more difficult to find.

I tried to approach this with performing mergesort on the $x$ points and then performing mergesort on the $y$ points and then comparing the two sets in some way. Then I get stuck.

Am I thinking about this correctly?

Answer 1

While divide and conquer and convex hull as suggested by others are good hints for this problem, this problem is actually simpler than that. (And also, the Convex Hull based solution is not actually correct, see this comment by Kevin Wang)

Here is a simple iterative solution.

1. Sort the points by x-axis.
2. Consider the point with the largest x-value. This point is definitely a Pareto-optimal point - right? Note down its y-value as the current highest y-value.
3. Go to the point with next lower x-value. If the y-value of this is greater than current best-value, then it is Pareto-optimal, otherwise it is not.
4. Keep doing it for all the points.

So, the time complexity is straightforward: O(n log n) for sorting by x, and O(n) for iterating the points after that.

If you are a pseudo-person, then you may like this pseudo-code.

Point[] inputList = input of points
Point[] sortedList = sortByXValueDescending (inputList)
List<Point> poPoints = new ArrayList<>(); // Output list - pareto optimal points
double currMaxY = NEG_INFINITY;
for (Point p: sortedList) {
  if p.getY() > currMaxY) {
     poPoints.add(p);
     currMaxY = p.getY();
  }
}

Answer 2

Hint: try to see this as a specific instance of computing the convex hull of a set a points (afterwards, it's not difficult to restrict the hull to the Pareto set). Then, you can for instance use Graham scan.

Answer 3

Try using Divide and Conquer . First Divide the problem into 2 instances by the x-median of the points. Recursively call the function for the right as well as the left halves. Then it is quite easy to merge the results of the two sub problems in linear time ( just observe, you will get it). So, the time complexity is:

$\qquad$ T($n$)=O($n$)+2T($\frac{n}{2}$)

$\qquad$ T($n$)=O($n \log{}n$)