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:
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) $$
$T=$ an empty set of $d-1$ dimensional vectors.
- 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"
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.