# 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.

• 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. – John L. Jan 27 '20 at 9:17

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.