Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.