1
$\begingroup$

I've been still analyzing one of function's algorithm(in any dimension) related to convex polytopes-polyhedrons for 6 days. According to the algorithm, it creates a cone but the point at which I'm stuck that why we need to create a cone and subcone(s). I'm studying on minkowski decomposition. Here is a definition and lemma but I have diffulty in grasping.

Some information related,

In this work, we compute instead all possible Minkowski summands. In the first step, we compute the cone of combinatorially equivalent polytopes $U(A)_{b}$ , a subcone of U(A) whose rays and lines generate all the Minkowski summands of $P_{b}$ . Then, we appropriately shift these rays so that they correspond to integer Minkowski summands. For more, source

enter image description here

For cube example, I have 6 points of cube which are [[0, 0, 1], [0, 1, 0], [1, 0, 0], [-1, 0, 0], [0, 0, -1], [0, -1, 0]]

enter image description here

They are put into matrix form,

$ \begin{pmatrix}0&0&1\\ 0&1&0\\ 1&0&0\\ -1&0&0\\ 0&0&-1\\ 0&-1&0\end{pmatrix} $

Then, the algorithm finds its kernel(null space).

$\begin{pmatrix}1\\ 0\\ 0\\ 0\\ 1\\ 0\end{pmatrix}\:,\:\begin{pmatrix}0\\ 1\\ 0\\ 0\\ 0\\ 1\end{pmatrix}\:,\:\begin{pmatrix}0\\ 0\\ 1\\ 1\\ 0\\ 0\end{pmatrix}$

and they are behaved as rays. Later, a polytope is created from the rays.

Now, an identity matrix is created and its columns are taken as rays. (orthant? if so why?)

$\begin{pmatrix}1\\ \:0\\ \:0\\ \:0\\ \:0\\ \:0\end{pmatrix}\:,\:\begin{pmatrix}0\\ \:1\\ \:0\\ \:0\\ \:0\\ \:0\end{pmatrix}\:,\:\begin{pmatrix}0\\ \:\:0\\ \:\:1\\ \:\:0\\ \:\:0\\ \:\:0\end{pmatrix},\:\begin{pmatrix}\:\:0\\ \:\:0\\ \:\:0\\ \:\:1\\ \:\:0\\ \:\:0\end{pmatrix}\:,\:\begin{pmatrix}0\\ \:\:0\\ \:\:0\\ \:\:0\\ \:\:1\\ \:\:0\end{pmatrix},\:\begin{pmatrix}0\\ \:\:0\\ \:\:0\\ \:\:0\\ \:\:0\\ \:\:1\end{pmatrix}$

Then, we intersect the two polytopes and again finds the intersected polytopes' rays.

Afterwards, the algorithm converts the intersected polytopes' rays into inequalities but all right hand sides are 0.

Finally, it creates a new polytope from the inequalities.

function createU(A):
    At= matrix(A).transpose()
    B = At.right_kernel()
    kern =Polyhedron(rays=B.gens())
    orthant = Polyhedron(rays=identity_matrix(len(A)).columns())
    pos_kern = kern.intersection(orthant)
    pos_ker_rays = pos_kern.rays()
    // adding zero for right hand side of all inequalities
    R= [ [0] + pos_ker_rays[i].vector().list() for i in range(len(pos_ker_rays))]
    P = Polyhedron(ieqs=R)
    return P
$\endgroup$

0

You must log in to answer this question.