3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think this answer has a flaw: If we are considering comparison-based model, we have no access to the exact value of $x_i$, let alone $-x_i$. $\endgroup$ – SolarTorch Mar 29 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.