Algorithm for maximum non-dominated set

Question

FInd an algorithm for the next problem : Given set S of n points in the 2D plane, a point (x1, y1) dominates another point (x2, y2) if x1 > x2 and y1 > y2. Find the largest set of points M such that M is a subset of S and no point of M is dominated by another point of S.

Answer 1

Sort all points by increasing x coordinates. If two points have the same x coordinate, sort them by decreasing y coordinates. Now, it can be shown that a subset of points is non-dominated if and only if their y coordinates are non-increasing in our sorted sequence, meaning each y coordinate is less than or equal to the previous one in the subsequence.

So the algorithm would be:

1. Sort the points as described above. Time: O(n*logn).
2. Find the longest non-increasing subsequence of y coordinates. Time: O(n*logn). This can be done by adapting the algorithm for finding the longest increasing subsequence.

This gives the largest possible set in O(n*logn).