This is an instance of finding the Pareto front [1] of a set of points in a two dimensional space. This problem is also known as "skyline queries"! According

This is an instance of finding the Pareto front [1] of a set of points in a two dimensional space. This problem is also known as "skyline queries"! According to [2], author's bound O(n log(n)) is the best bound for d=2. [1] http://en.wikipedia.org/wiki/Pareto_efficiency http://en.wikipedia.org/wiki/Pareto_efficiency [2] http://pdf.aminer.org/000/211/201/on_the_computational_complexity_of_finding_the_maxima_of_a.pdf http://pdf.aminer.org/000/211/201/on_the_computational_compl...