Return to Revisions

Here is a simple polynomial algorithm. Transform your outer parallelepiped to the cube $[-1,1]^N$ by the affine map $$A: x \mapsto 2 V^{-1}(x-x_0) - \mathbf{1},$$ where all components of $\mathbf{1}$ are 1 and $$V = (v_1,v_2,\ldots,v_N).$$ $A$ maps the base $x_1$ of your second parallelepiped to $\xi_1$ and its spanning vectors $w_1,\ldots,w_N$ become $$ \omega_k=2 V^{-1} w_k.$$ The second parallelepiped is inside the first iff for the maximum norm $$\|\xi_1 + t_1 \omega_1 +\ldots + t_N \omega_N \| \leq 1 $$ for all $t_k \in [0,1]$. Because in the extremal cases $t_k \in \{ 0,1 \},$ the condition can be easily checked componentwise. For the $m$-th component one just has to check whether the sum of all positive entries of $\xi_{1,m}$ and $\omega_{k,m}$ is $\leq 1$, and the sum of all negative entries of $\xi_{1,m}$ and $\omega_{k,m}$ is $\geq -1$.