Page 1 of 1

Convex Decomposition

Posted: 12 Jan 2022, 07:34
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!

Re: Convex Decomposition

Posted: 12 Jan 2022, 09:30
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?

Re: Convex Decomposition

Posted: 12 Jan 2022, 10:29
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.

Re: Convex Decomposition

Posted: 12 Jan 2022, 12:04
That does not have unique solutions. Instead the set of such solutions forms a polyhedron in the parameter space (= coefficients of the linear combinations).

Re: Convex Decomposition

Posted: 12 Jan 2022, 16:14
Thank you again for the response. For my purposes any decomposition might suffice, but this suggestion about the coefficients may be quite useful Re: Convex Decomposition

Posted: 13 Jan 2022, 13:20
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