Uniqueness of non-dominated two-dimensional points 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.
For $n=1$ the statement is trivially true. Otherwise $n &gt; 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 &lt; 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 &lt; 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 &lt; 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.