I thought of one way to do this. Using the algorithm which determines if a point is inside a parallelogram, one can determine if the polygon contains the point within $2N$ steps ($N=2$ for parallelogram) I want to do this for $n$-dimensional parallelotope but I guess it will take $2^N$ check for every vertex of the $n$-parallelotope. Could somebody suggest a better way, which is computationally faster (in a polynomial time, not exponential)?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Are the parallelotopes based at the origin? Here's a guess, which might not be right. An $n$-dimensional parallelotope (based at the origin) is generated (i.e., as a zonotope) by $n$ linearly independent vectors. Say you have one set of vectors $\{v_1,\ldots,v_n\}$ corresponding to one parallelotope, and another $\{w_1,\ldots,w_n\}$ corresponding to another. Maybe it's the case that we have a containment of parallelotopes if and only if $\{w_1,\ldots,w_n\}$ is contained in the simplex generated by $\{v_1,\ldots,v_n\}$ and the origin. $\endgroup$– Sam HopkinsCommented Jun 3, 2021 at 13:55
-
$\begingroup$ This question is somewhat related: mathoverflow.net/questions/279021 $\endgroup$– Neil StricklandCommented Jun 3, 2021 at 14:26
-
$\begingroup$ @MattF. In my algorithm, I use a generator that has a vertex $x_0$ as a reference point of the parallelotope and n linearly independent vectors $v_k (\forall{k=1,..,n})$as bases. ( $P=\{x_0,v_1,v_2, .. , v_n\}$ for $n$-dim.). In this way, I can operate a parallelotope at the $n$-dimensional space using an affine transform in $n+1$ linear calculation. $\endgroup$– sykCommented Jun 4, 2021 at 6:42
-
$\begingroup$ @SamHopkins You're right if they share the same origin, but in my case, the parallelotopes can have arbitrary location and shape. Please refer to my previous answer above. $\endgroup$– sykCommented Jun 4, 2021 at 7:38
-
$\begingroup$ @syk, it would help for the post to state explicitly how the algorithm should respond in these examples: 1) Is the parallelogram at $(0,0)$ with basis vectors $2i$ and $4j$ contained in the parallelogram at $(1,0)$ with basis vectors $3i$ and $5j$? 2) Is the parallelogram at $(0,0)$ with basis vectors $2i$ and $4j$ contained in the parallelogram at $(0,0)$ with basis vectors $5i$ and $3j$? $\endgroup$– user44143Commented Jun 4, 2021 at 12:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
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$. Update: This means for all $1\leq m \leq N$: $$ \xi_{1,m}+\sum \limits_{k=1}^N \max(0,\omega_{k,m})~\leq 1,$$ $$ \xi_{1,m}+\sum \limits_{k=1}^N \min(0,\omega_{k,m})~\geq -1.$$
