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

Answer 2

There is a divide and conquer algorithm which does this in O(n*logn) time.

Let's divide the points into two halfs, of size n/2 each, based on their x co-ordinates. We find the non-dominated point set in both the halfs. You need to observe that all the non-dominated points found in the right half will exist in our final list.

With this observation we can write our combine step, remove all the non-dominated points in the left half which have y co-ordinate less than highest y co-ordinate of the point in the non-dominated set in the right half. We have the set of non-dominated points.

Algorithm:

Find the median along x axis - O(n) time
Find non-dominated points in the left half - T(n/2) 
Find non-dominated points in the right half - T(n/2)
set of non-dominated points could be on O(n) so, the combine step might have to check O(n) points

Equation for time :

 T(n) = 2T(n/2) + O(n) which is O(n*logn)

You can improve this further to O(n*logH) where H is the number of non-dominated points, it requires more insight into the problem and it is a good extension for you to work on.