# On finding the nondominated set of vectors. How to understand this algorithm?

L et us denote by $x_i(v)$ the $i$th coordinate of $v \in \mathbb{R}^d$.
Then $v = \left [ x_1(v), x_2(v), \dots ,x_d(v) \right ]$

We say that a $v \in \mathbb{R}^d$ dominates another vector $w \in \mathbb{R}^d$ if

$$\forall i \in \left \{1, 2, \dots, d \right \}: x_i(v) \geq x_i(w)$$

We have a set of $d$ dimensional vectors $S = \left \{ v_1, v_2, \dots , v_n \right \}$. We call a vector $nondominated$ if it is not dominated by any other vector in $S$.

I found the following recursive algorithm to find all the nondominated vectors in $S$.

Notation:
Let us denote by $v^*$ the projection of $v$ to axes $2,3, \dots, d$. That is $v^* := \left [ x_2(v), \dots ,x_d(v) \right ]$

Let $T$ be a set of $d - 1$ dimensional vectors and $u$ be some other $d - 1$ dimensional vector. Then by $u \prec T$ we mean that there is a vector $q \in T$ such that $q$ dominates $u$.

$S = \left \{ v_1, v_2, \dots , v_n \right \}$ is the set of vectors whose nondominated subset we are trying to find. We assume that no two vectors have the same value in any coordinate.

Agorithm:

1. arrange (change indices) the elements $S = \left \{ v_1, v_2, \dots , v_n \right \}$ by their first coordinate from the maximal until the minimal: $$x_1(v_1) > x_1(v_2) > \dots > x_1(v_n)$$

2. $T=$ an empty set of $d-1$ dimensional vectors.

3. for $i = 1$ to $n$ do:
if ($v_i^* \nprec T$) T = the set of nondominated vectors in $T \bigcup v_i^*$
i++

The autors claim that a vector $v$ is nondominated in $S$ iff $v^* \in T$.

I understand why all the vectors $v$ for whom $v^* \in T$ are nondominated in $S$. But why should all the nondominated vectors satisfy $v^* \in T$?

I am especially concerned about: $$T = \text{the set of nondominated vectors in } T \bigcup v_i^*$$ step of the algorithm. Why does $v_i$ have the right to throw out vectors out of $T$? Suppose that $v = \left [ -\infty , \infty , \infty , \dots, \infty \right ]$. Then $v$ would be the last vector in the sequence, it would pass the check for $v \nprec T$ and it would make: $$T = \text{the set of nondominated vectors in } T \bigcup v$$ equal to $\left \{ v \right \}$, even if there was some other nondominated vector.

What am I missing here? Did I misunderstand the algorithm in some way?

EDIT:

The original article is:

On finding the maxima of a set of vectors (1975) by H. T. Kung , F. Luccio , F. P. Preparata

Algorithm presented here is a paraphrased Algorithm 3.1 in the article. The only major difference is that they use the term "maximum" and I use "nondominated" • It might help if you could state the reference from which you got this, both algorithm and claim.
– MvG
Aug 1 '13 at 7:05
• Note that the article has $T_i$ consisting of $v_j^*$, i.e. truncated verctor, whereas your notation uses $v_i$, untruncated ones. Yours makes more sense to me: in that case, newer elements would “throw out” older ones only if the first coordinate were the same and the newer vector dominated the older one. Your formulation of step 1 does allow such equal coordinates, while the paper does not. On the whole, I see little point in this approach: if you do maximality checks all over the place, you might as well write “if $v_i\not\prec T$ set $T\leftarrow T\cup\{v_i\}$” as the only step in a loop.
– MvG
Aug 1 '13 at 7:56
• @MvG I am sorry, it was a mistake on my part. The algorithms are supposed to be 100% same. I corrected it and changed to sharp inequalities. Aug 1 '13 at 8:39

If I do not err the Theorem 3.1 from the JACM '75 paper by Kung, Luccio and Preparata that you mention has a typo and should read: "$v_i$ is a maximal element of $V$ iff $v_i^*$ in $T_i$".
The argument for the correctness of the "patch" is that $v_i^*$ is inserted into $T_i$ iff $v_i^*$ is not dominated by $T_{i-1}$, or equivalently, $v_i$ is not dominated by any vector $v_j$ with $j<i$.
It may happen that $v_i^*$ gets dominated by $v_j^*$ for some $j>i$ in subsequent steps, as in your example. But vectors $v_j$ with $j>i$ cannot dominate $v_i$ since they are smaller on the first component.
• I think that is not the case. The final set $T_n$ is supposed to contain all the maxima. But I think the problem is the step $T_i \leftarrow maxima\left ( T_{i-1} \bigcup v_i^* \right )$. As MvG suggested, this is likely the faulty step. If you replace it with $T_i \leftarrow T_{i-1} \bigcup v_i^*$ the algorithm seems correct. If I have time, I will dig in their references and update if I find something interesting. Aug 21 '13 at 12:58
• 2a) However MvG's suggestion is not exactly what you refer to: he suggests to maintain a set of 3-D vectors. The trouble with that (and also with your adaptation by projecting onto 2 components) is : how will you check efficiently $v_j< T$ (if you store 3D vectors) or $v_j^*< T$ (if you store 2D vectors as proposed by the paper) in the subsequent steps? Aug 21 '13 at 13:31
• 2b) If you keep only $maxima(T_{i-1}\cup v_i^*)$ then it is easy to do so using the AVL structure described by the paper on the next page. This is because when you order a set of maximal vectors according to first component, the second component is sorted in inverse order. If you keep more than the maxima in $T_i$, this property is lost so you need to adapt the algorithm. The patch I suggest allows to keep the proof "as is". Aug 21 '13 at 13:32