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 [2] http://pdf.aminer.org/000/211/201/on_the_computational_compl...