In some other question regarding basis selection a surprising solution came up, where we construct the convex hull of the given points and then shoot a specific ray from the origin. The corners of the facet that got hit first, will be the selected basis. But constructing the whole convex hull is not feasable, within my framework. Thus I am looking for a way to quickly intersect a ray with a convex hull. Now let's describe the problem more concretely:
Let $\vec a_1, \dots, \vec a_n \in \mathbb{N}^m \setminus \{\vec 0\}$ be arbetrairy and $C$ be its convex hull. Let $\vec b \in \mathbb{N}^m \setminus \{\vec 0\}$ be some vector such that there exists $\lambda_1, \dots, \lambda_n \in \mathbb{N}$ such that $\vec b = \lambda_1\vec a_1 + \dots +\lambda_n\vec a_n$. This implies that $\vec b$ is always "behind" $C$ when viewed from the origin and thus the ray $R := \{\gamma\vec b\mid \gamma \in \mathbb{R}_{\geq 0}\}$ will always intersect $C$ at some point $\vec p$ (I want the first intersection, so the front face). Let $\vec a_{j_1}, \dots, \vec a_{j_r}$ be the corners of the facet of $C$ that intersects $R$ first.
My question is: Is there a way to obtain $\vec a_{j_1}, \dots, \vec a_{j_r}$ without constructing the whole convex hull. I feel like being interested in just one point (the point of intersection) or one facet (the facet of intersection) should simplify the problem significantly. But I have no idea how to tackle that problem.
In the example below the vectors $\vec a_1$ and $\vec a_8$ would be the ones, I am interested in.
I figured it out by myself. My question is basically an variation on the question whether a single point is inside a convex hull. This is just an adapted version of this answer.
Let's start with the one fact, I found here: If my $\vec a_1, \dots, \vec a_n$ are affine independent, then any vector $\vec p \in C$ can be represented as an unique affine combination of $\vec a_1, \dots, \vec a_n$. Let's first assume that they are and handle a possible dependence later. Remember that a affine combination is a linear combination $\vec p = \lambda_1\vec a_1 + \dots + \lambda_n\vec a_n$ where $\lambda_1 + \dots + \lambda_n = 1$ and $\lambda_j \geq 0$. Because the $\vec p$ we are seeking lies on a facet, and thus on the affine space of the corners of that facet, we know that there exists an affine combination of just the corners to arrive at $\vec p$. And as the affine combination of all $\vec a_j$ is unique, we know that in this affine combination, all coefficiants of all unrelated $\vec a_j$ are zero. This means, that if we found the $\vec p = \gamma\vec b$, that lies on the facet, we just have to figure out its affine combination and all $\vec a_j$'s whos coefficiant is non-zero will be a corner of the facet we are interested in.
But how do we find that exact $\vec p$. For that, the abovementioned answer was super helpful. We can just create a linear program, for that task and a linear program can be solved exactly in polynomial time, e.g. using the Ellipsoid Method, which is super nice. Let's construct our linear program:
Let $A := (\vec a_1, \dots, \vec a_n, -\vec b) \in \mathbb{N}^{m \times (n+1)}$ the matrix, where in the $j$-th column is $\vec a_j$ and the last column is $-\vec b$. Let $\vec x := (\lambda_1, \dots, \lambda_n, \gamma)^\top$ be our vector of unknowns. Let $\langle \cdot\mid\cdot\rangle$ be the standart dot-product. Then the linear program becomes: \begin{align} \text{Minimize:}&&\quad \langle (0, \dots, 0, 1&)^\top\mid\vec x\rangle &&\quad= \gamma\\ \text{Subject to:}&&\quad A\cdot\vec x &= \vec0 &&\quad \Leftrightarrow \lambda_1\vec a_1 + \dots + \lambda_n\vec a_n = \gamma \vec b\\ && (1, \dots, 1, 0)\cdot \vec x &= 1&&\quad\Leftrightarrow \lambda_1 + \dots + \lambda_n = 1\\ && \vec x &\geq \vec0 &&\quad\Leftrightarrow \lambda_j \geq 0, \gamma \geq 0 \end{align} By minimizing $\gamma$, we make sure, to receive the first point of intersection of $R$ and $C$. From the result, we can read of everything we need, as the resulting $\vec x$ will give us the affine combination of $\vec p$ and also $\vec p = \gamma \vec b$ itself.
What would be the consequence of an affine dependence? We would still get the right $\gamma$ and thus $\vec p$ but the affine combination might not be unique. For us, that only happens if more $\vec a_j$'s than the facet's corners lie in their affine space. This might result in an affine combination, where more coefficiants than expected are non-zero. To fix that, I can just select an affine basis from those $\vec a_j$'s, whose coeffiants are non-zero. That would be enough for me.