As other answers have pointed out, the worst case complexity is O(n^2).
However, there are heuristics that can help a lot in practice. For example if the set A is a subset of Z^2 (integer pairs), then we can eliminate a lot of points upfront by:
- Sorting along the x-axis (for a given x-value say 1, find the point
with max y-value, repeat for all x-values) to get a candidate set of
maximals, call it y-maximals.
- Similarly get the set x-maximals.
- Intersect to get final candidate set xy-maximals.
This is of cost O(n). It is easy to see that any maximal point will be present in xy-maximals. However, it can contain non-maximal points. For example, consider the set {(1,0), (0,1), (2,2)}.
Depending on your situation, this may be a good enough heuristic. You can follow this up with the exhaustive algorithm on the smaller set xy-maximals.
More generally, this problem is called the 'Pareto Frontier' calculation problem. Here are good references:
http://www.cs.yorku.ca/~jarek/papers/vldbj06/lessII.pdf
https://en.wikipedia.org/wiki/Pareto_efficiency#Use_in_engineering_and_economics
In particular the BEST algorithm from the first reference is quite useful.