Convex Decomposition

General discussion on polymake goes here.
selman.ipek
Posts: 4
Joined: 25 Oct 2021, 12:47

Convex Decomposition

Hi All, I have the vertices for two polytopes $P_1$ and $P_2$. Mathematically I know that that $P_2 \hookrightarrow P_1$ and would like to decompose the vertices of $P_2$ in terms of embedding $P_1$. Any suggestions on how to do this? Can polymake help? I couldn't find anything in the manual. Alternative software suggestions also welcome, thanks!

joswig
Main Author
Posts: 254
Joined: 24 Dec 2010, 11:10

Re: Convex Decomposition

Sorry, I don't understand the question.

Is it that P_2 is a subpolytope of P_1, and you want to find those vcertices of P_1 which are not vertices of P_2?

selman.ipek
Posts: 4
Joined: 25 Oct 2021, 12:47

Re: Convex Decomposition

Hi, thanks for the response. The problem is that since P2 is a properly embedded in P1 I would like to express the vertices of P2 as a convex sum of the vertices of P1.

joswig
Main Author
Posts: 254
Joined: 24 Dec 2010, 11:10

Re: Convex Decomposition

That does not have unique solutions. Instead the set of such solutions forms a polyhedron in the parameter space (= coefficients of the linear combinations).

selman.ipek
Posts: 4
Joined: 25 Oct 2021, 12:47

Re: Convex Decomposition

Thank you again for the response. For my purposes any decomposition might suffice, but this suggestion about the coefficients may be quite useful

opfer
Developer
Posts: 80
Joined: 04 Feb 2013, 11:12

Re: Convex Decomposition

Isn't this just solving a linear program $V_1 \cdot x = v_{2,i}$, $x>=0$, $\sum_j x_j = 1$ for each vertex $v_{2,i}$ of $P_2$ ($V_1$ being the Matrix containing the vertices of $P_1$, $x$ being the coefficients of a possible convex combination)? Any LP solver (including Polymake) should be able to do this.

Best regards,
Thomas