title: Dominant set of points in O(n)
body: <p>So, if two points A(x1,y1) and B(x2,y2) are given, and if x1 &lt;= x2 and y1&lt;= y2, then we say B dominates A. Now, given a lot of points, I wish to find out all the non-dominated points. Trivial approach is compare every point with others and get all non-dominated points. But it's O(n^2). So I tried divide and conquer, pretty straightforward and I get to find that in O(nlogn). Our professor says, it can still be done in O(n). I kind of think it's really not possible. I'm not asking you to solve this for me, but would like to know if there's any 'obvious' way through which I can be sure that it can't be done in O(n) under any conditions? However, if it's really possible, don't answer, maybe give some clue.</p>