Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane.
A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$.
A point is called a maxima if no other points dominate it.
I can come up with an $O(n \log n)$ algorithm to find all the maxima. However, I failed to solve:
Problem: What is the lower bound for the "finding all 2D maxima" problem (say, on the comparison model)? And how to prove it?
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 > 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) > (y,j)$ if $x > y$ or $x=y$ and $i > 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.
