0
$\begingroup$

I have a list of thousands 3D vectors $(x_i, y_i, z_i)$. These are too many to work with so i want to reduce their number. For that cause, i implemented the following criterion:

If a $j$ exists such that:

  • $x_j \le x_i$ and
  • $y_j \le y_i$ and
  • $|z_j| \ge |x_i|$

then vector $i$ gets eliminated from the list.

My question now is whether the number of vectors produced by the aforementioned elimination process is bounded or not.

If the number of vectors surving is $k$ and the original population $p$, is there an $n$ such that:

$p > n \ge k$ ?


PS: I wrote a program in python for this and managed to reduce the number of vectors significantly. I tried it in a lot of sets and indicatively i got from ~75000 to ~100. In some cases i got more than 200 though (216 to be exact) which seems a bit too many..

$\endgroup$
1
$\begingroup$

$k$ need not be bounded. Consider the following infinite set of vectors. $S=\{\langle x,x,x \rangle \mid x\in\mathbb{Z}, x > 0 \} = \{\langle 1,1,1 \rangle, \langle 2,2,2 \rangle,\langle 3,3,3 \rangle, \dots \}$.

None of the vectors in $S$ may be eliminated by the process you describe. The same holds for any subset of $S$ including finite subsets.

$\endgroup$
  • 1
    $\begingroup$ that was more obvious than I expected it to be ☺. Thanks! $\endgroup$ – Ev. Kounis Nov 14 '16 at 13:17
  • $\begingroup$ There might be a more difficult probability question in there along the lines of: If a set of x many vectors which are randomly selected using this given distribution are subject to the following elimination rule (in which you need to explain in what order the $i$ and $j$s are selected for comparison), what is the expected size of the remaining set of vectors when this elimination rule can no longer be applied. Since I know little probability theory I couldn't solve such a question, but there might be someone who can. $\endgroup$ – Aydin Gerek Nov 14 '16 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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