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

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.

• Your approach actually comes pretty close. You don't need to do the second sort on y-points. Just the sort on x-points is enough. Then, just iterate and collect the good points in O(n) time. For details, see the answer below. Commented Sep 22, 2016 at 20:42

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) {
currMaxY = p.getY();
}
}

• Thank you. In lots of software, you can also sort descendingly by (X, Y) (lexicographically), and this would ensure that you only have one point with max X - the one with the max Y among them. Commented Nov 6, 2020 at 18:07

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.

• I thought this was true as well, but I don't think it's actually true. For example, given the points (0,3), (3,0), (0,0), (1,1), (1,1) would not be on the convex hull, but would be in the Pareto set. See: C in this diagram: commons.wikimedia.org/wiki/… Commented May 14, 2020 at 1:22

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$)

• How do you write your merge function in O(n)? Commented May 23, 2017 at 8:31