Lower bound for maxima on 2D plane
When asking for a lower bound, you should let us know what computation model you're interested in. A good first model to prove lower bounds on is the comparison model. In this case, usually you use the fact that given $n$ values $x_1,\ldots,x_n$, determining whether all of them are unique takes $\Omega(n\log n)$ comparisons. This problem is known as element distinctness or element uniqueness.

In your case, the natural candidate reduction is to map $x_i$ to $(x_i,-x_i)$. Note that no pair dominates each other, but if $x_i = x_j$ then $(x_i,-x_i)$ "weakly dominates" $(x_j,-x_j)$. Therefore any algorithm outputting the number of "weak maxima" can be used to decide element uniqueness, and so requires $\Omega(n\log n)$ comparisons.

You are interested in maxima rather than weak maxima, so you need to tweak this idea a bit. Suppose that all $x_i$ were integers. Then you map $x_i$ to $p_i = (x_i+i/(2n),-x_i+i/(2n))$. Now $p_i$ dominates $p_j$ iff $x_i = x_j$ and $i &gt; j$. So the number of maxima again allows you to decide element uniqueness.

While you can't really assume that the $x_i$ are integers in the comparison model, you can tweak the reduction even further to implement the same effect: you map $x_i$ to $p_i = ((x_i,i),(-x_i,i))$, and you compare pairs of the form $(x,i)$ according to the following rule: $(x,i) &gt; (y,j)$ if $x &gt; y$ or $x=y$ and $i &gt; j$. Every algorithm for computing the number of maximas in the comparison model using $m$ comparisons can be converted to an algorithm for deciding element uniqueness using $O(m)$ comparisons, hence requires $\Omega(n\log n)$ comparisons.