2
$\begingroup$

Since I'm studying on Minkowski Decompositon for my undergraduate thesis(Comp.Sci) I need advices, ways, procudures etc. from you, dear, mathematicians. I'm indeed stuck because of a lot of suppositional mathematical notations in a way. Let me explain what I'm trying to get.

We have a polytope which is result of summands of two another polytopes known as Mikowski Summand. Let's go ahead with visual examples.

enter image description here

For square(a polytope)

$ A\:=\:\begin{pmatrix}-1&0\\ 0&-1\\ 0&1\\ 1&0\\ \end{pmatrix},\:b\:=\:\begin{pmatrix}0\\ 0\\ 1\\ 1\\ \end{pmatrix} $

For triangle(the other polytope)

$ A\:=\:\begin{pmatrix}-1&0\\ 0&-1\\ 1 &1\end{pmatrix},\:b\:=\:\begin{pmatrix}0\\ 0\\ 1 \end{pmatrix} $

For resulting polytope

$A\:=\:\begin{pmatrix}-1&0\\ 0&-1\\ 0&1\\ 1&0\\ 1&1\end{pmatrix}$ , $\:b\:=\:\begin{pmatrix}0\\ 0\\ 2\\ 2\\ 3\end{pmatrix} $

It's the visualization of Minkowski Sum. My task is to obtain(extract, decompose) the two polytopes which are parts(components or what you say) of the resulting polytope. Assume that we only have for $Ax\leq \ b$, A and b matrices of the resulting(integrated, composed) polytope. And get its components which are the two polytopes.

enter image description here

We should watch out two things. As you can see, the are 3 Rs, AFAIG, they represent bs. The first is that the matrix presentation(H-representation) of resulting polytope includes its component polytope's matrices values. I mean that [-1,0],[0,-1],[1,1],the triangle, is included in resulting polytope's that [-1,0],[0,-1],[0,1],[1,0],[1,1]. Same thing is applied for the other addend polytope. The second is that I put some numbers in green rectangle. If you pay carefully attention to the values which are not initially there, we don't know the values, think them as blanks, we figure out(inference) the values later on. How can we accomplish it? How can we determine the addends' coordinates? For example, triangle's don't include [1,0] and [0,1] but [-1,0],[0,-1],[1,1]. En passant, the polytopes are not restricted with merely 2D, they can be 3D,4D,5D or higher. As far as I listen my lecturer and google, I get ,related to my subject, Fourier-Motzkin Elimination, normal fan, cone, rays, hyperplane, Farkas lemma, H-representation, V-representation but they seem verily very strange for me. Consequently, I'd like to listen your ideas and advices for me. I'm indebted to everybody already now.

$\endgroup$

0

You must log in to answer this question.