0
$\begingroup$

This question is a nice variant of How to compare n number of m-dimensional points among one another with minimum time complexity? for two dimensions.

We say point $p_i=(x^i_1, x^i_2)$ dominates point $p_j=(x^j_1, x^j_2)$ if $x^i_1 \geq x^j_1$ and $x^i_2 \geq x^j_2$. Prove that if in a set of $n$ points there are no pairs such that one dominates the other, that the points can be ordered such that one dimension is strictly ascending and the second is strictly descending.

Improve this question
$\endgroup$
1
  • $\begingroup$ If $(x_1,y_1)$ and $(x_2,y_2)$ is a non-dominated pair, then $x1\neq x_2$, $y_1\neq y_2$, and the order of $y_1$ and $y_2$ must be reverse to that of $x_1$ and $x_2$. So if the points are ordered by $x$ coordinate, then they must be reversely ordered by $y$ coordinate. $\endgroup$
    – John L.
    Commented Jan 27, 2020 at 9:17

1 Answer 1

Reset to default
1
$\begingroup$

For $n=1$ the statement is trivially true. Otherwise $n > 1$.

Sort the points in each dimension in ascending order. Let $r^i_1, r^i_2$ be the rank of point $i$ in each dimension, rounding ties down. (Thus if there is a duplicate value (1,2,2,3) we take the index of the first appearance in the list). We use 0-based indexing.

First we note that for a point $p_i$ that $w_i = r^i_1 + r^i_2$ gives an upper bound on the number of points that can't dominate $p_i$. Therefore, by a counting argument, if $w_i < n-1$ there must be a point that dominates $p_i$.

We will now assume that we have a set of points that doesn't have a dominated pair. For convenience, we rename all the points such that they are ordered in the first dimension, thus $p^0_1 \leq p^1_1 \leq \dots p^{n-1}_1$.

We will now prove that $r^i_1 = i$ and $r^i_2 = n - 1 - i$.

Clearly $r^0_1 = 0$. Therefore, $r^0_2 = n-1$, otherwise $w^0 < n-1$, and there is a point dominating $p_0$. Since $r^0_2 = n-1$ there is no point having the same value in the second dimension (otherwise, $r^0_2 < n-1$).

Assume that we have proved for the first $j$ points, we now prove for $j+1$. Note that since each of the first $j$ points have $r^i_2 = n-1 - i$, this means that there are no other points having those rankings. Since the points are in ascending order in the first dimension, $r^{j+1}_1 = j$ or $r^{j+1}_1 = {j+1}$. Let us assume by contradiction the former. Therefore, since there are no dominated pairs, we have that $r^{j+1}_2 \geq n - 1 - j$, which is a contradiction (to no other points having those rankings). Therefore, $r^{j+1}_1 = {j+1}$ and since there are no dominated pairs, $r^{j+1}_2 = n - 1 - {j+1}$, and no other point may have that value.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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