# Maximize 2-tuple efficiently

Hello I am lookin for an algorithm that efficiently finds all Tuples ${(x,y)$$\varepsilon U|\forall (u,w) \epsilon U \rightarrow (x>=u \vee y>=w)$.

I could of course check all tuples against any other tuple but this would give me an O(n^2) performance. And even if I do this in a smarter way, I do not seem to get past O(n^2).

Thanks Benedikt

-
This website is for questions of mathematical research interest. I suspect your question does not qualify, and might get a better reception at a coding site. –  Gerry Myerson Mar 20 '13 at 5:15

I indeed doubt that this is really of a research nature, but I can't be sure.

Anyway, if you first run through all your tuples, you can determine the maximum for both coordinates in $O(n)$. Afterwards you run through your tuples a second time and you can get all the tuples where one of the coordinates is equal to the maximum in $O(n)$.

-
Maybe I missunderstood you but this is not what I mean. If I had the uples 10, 2 5, 4 3, 3 4, 7 5, 6 1, 9 My candidates would be (10,2),(4,7) (5, 6) (1,9) because for none of these tuples there exists another tuple that has both coordinates bigger than itself. –  user32352 Mar 25 '13 at 22:52
No, in that case I misunderstood your question. I'll think about it. –  nvcleemp Mar 29 '13 at 6:18
I gave it another thought and I think I found something that is better than $O(n^2)$. I have added it as a new answer, since it is quite different from this answer, and it might be interesting for later reference what the misinterpretation was. –  nvcleemp Apr 5 '13 at 7:24

OK, I think I found something this time.

We start by sorting the tuples based on the first element. This can be done in $O(n\log n)$.

The first tuple of the sorted list is certainly in your set. The second tuple is in your set if the second element of that tuple is larger than or equal to the second element of the first tuple. And more generally: any tuple in the list is in the set if its second element is larger than or equal to the maximum of the second elements of the previous tuples. So you can go through the list, storing the maximum of the second elements as you go along and add each tuple to the set if its second element is larger than or equal to the maximum you have at that point. This has complexity $O(n)$.

This gives a total complexity of $O(n\log n)$.

-