Mixing
Polytope in Minkowski sum
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Is the following statement true?
Suppose that $P$ is a polytope contained in the Minkowski sum $A+B:=a+b: ain A, bin B$ of two convex compact sets $A$ and $B$. Then there exist polytopes $Qsubset A$ and $Rsubset B$ such that $P = Q+R$.
Edit: Here's my attempt. Let $P$ be the convex hull of its extreme points $v_1,ldots, v_kin A+B$. Then by definition of the Minkowski sum, for $1leq ileq k$ there exist $a_iin A$ and $b_iin B$ such that $v_i = a_i + b_i$. Let $R$ be the convex hull of the $a_i$ and let $Q$ be the convex hull of the $b_i$. Then $Rsubset A$ and $Qsubset B$.
Does it follow that $P=Q+R$?
Update: It is true and compactness is not needed. I will post in the answer. Thank you.
convex-analysis convex-geometry polytopes
asked Jul 22 at 21:51
user3816
977
add a comment |Â
up vote
1
down vote
favorite
Is the following statement true?
Suppose that $P$ is a polytope contained in the Minkowski sum $A+B:=a+b: ain A, bin B$ of two convex compact sets $A$ and $B$. Then there exist polytopes $Qsubset A$ and $Rsubset B$ such that $P = Q+R$.
Edit: Here's my attempt. Let $P$ be the convex hull of its extreme points $v_1,ldots, v_kin A+B$. Then by definition of the Minkowski sum, for $1leq ileq k$ there exist $a_iin A$ and $b_iin B$ such that $v_i = a_i + b_i$. Let $R$ be the convex hull of the $a_i$ and let $Q$ be the convex hull of the $b_i$. Then $Rsubset A$ and $Qsubset B$.
Does it follow that $P=Q+R$?
Update: It is true and compactness is not needed. I will post in the answer. Thank you.
convex-analysis convex-geometry polytopes
asked Jul 22 at 21:51
user3816
977
1
At first sight it seems true to me. Considering that $P$ is the convex hull of finitely many points in $A+B$ we could easily write any point in $P$ as the sum of points in two different convex hulls. Something like $p=sum_iin Ilambda_i(a_i + b_i)=sum_iin Ilambda_i a_i +sum_iin Ilambda_i b_i$ may work it out. If you have any attempt of your own maybe it will be easier to help!
– Ariel Serranoni
Jul 22 at 22:13
Thank you for your comment. I updated the post with my attempt.
– user3816
Jul 22 at 22:36
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Is the following statement true?
Suppose that $P$ is a polytope contained in the Minkowski sum $A+B:=a+b: ain A, bin B$ of two convex compact sets $A$ and $B$. Then there exist polytopes $Qsubset A$ and $Rsubset B$ such that $P = Q+R$.
Edit: Here's my attempt. Let $P$ be the convex hull of its extreme points $v_1,ldots, v_kin A+B$. Then by definition of the Minkowski sum, for $1leq ileq k$ there exist $a_iin A$ and $b_iin B$ such that $v_i = a_i + b_i$. Let $R$ be the convex hull of the $a_i$ and let $Q$ be the convex hull of the $b_i$. Then $Rsubset A$ and $Qsubset B$.
Does it follow that $P=Q+R$?
Update: It is true and compactness is not needed. I will post in the answer. Thank you.
convex-analysis convex-geometry polytopes
asked Jul 22 at 21:51
user3816
977
Is the following statement true?
Suppose that $P$ is a polytope contained in the Minkowski sum $A+B:=a+b: ain A, bin B$ of two convex compact sets $A$ and $B$. Then there exist polytopes $Qsubset A$ and $Rsubset B$ such that $P = Q+R$.
Edit: Here's my attempt. Let $P$ be the convex hull of its extreme points $v_1,ldots, v_kin A+B$. Then by definition of the Minkowski sum, for $1leq ileq k$ there exist $a_iin A$ and $b_iin B$ such that $v_i = a_i + b_i$. Let $R$ be the convex hull of the $a_i$ and let $Q$ be the convex hull of the $b_i$. Then $Rsubset A$ and $Qsubset B$.
Does it follow that $P=Q+R$?
Update: It is true and compactness is not needed. I will post in the answer. Thank you.
convex-analysis convex-geometry polytopes
asked Jul 22 at 21:51
user3816
977
edited Jul 23 at 0:08
asked Jul 22 at 21:51
user3816
977
asked Jul 22 at 21:51
user3816
977
asked Jul 22 at 21:51
user3816
977
977
1
At first sight it seems true to me. Considering that $P$ is the convex hull of finitely many points in $A+B$ we could easily write any point in $P$ as the sum of points in two different convex hulls. Something like $p=sum_iin Ilambda_i(a_i + b_i)=sum_iin Ilambda_i a_i +sum_iin Ilambda_i b_i$ may work it out. If you have any attempt of your own maybe it will be easier to help!
– Ariel Serranoni
Jul 22 at 22:13
Thank you for your comment. I updated the post with my attempt.
– user3816
Jul 22 at 22:36
add a comment |Â
1
At first sight it seems true to me. Considering that $P$ is the convex hull of finitely many points in $A+B$ we could easily write any point in $P$ as the sum of points in two different convex hulls. Something like $p=sum_iin Ilambda_i(a_i + b_i)=sum_iin Ilambda_i a_i +sum_iin Ilambda_i b_i$ may work it out. If you have any attempt of your own maybe it will be easier to help!
– Ariel Serranoni
Jul 22 at 22:13
Thank you for your comment. I updated the post with my attempt.
– user3816
Jul 22 at 22:36
1
1
At first sight it seems true to me. Considering that $P$ is the convex hull of finitely many points in $A+B$ we could easily write any point in $P$ as the sum of points in two different convex hulls. Something like $p=sum_iin Ilambda_i(a_i + b_i)=sum_iin Ilambda_i a_i +sum_iin Ilambda_i b_i$ may work it out. If you have any attempt of your own maybe it will be easier to help!
– Ariel Serranoni
Jul 22 at 22:13
At first sight it seems true to me. Considering that $P$ is the convex hull of finitely many points in $A+B$ we could easily write any point in $P$ as the sum of points in two different convex hulls. Something like $p=sum_iin Ilambda_i(a_i + b_i)=sum_iin Ilambda_i a_i +sum_iin Ilambda_i b_i$ may work it out. If you have any attempt of your own maybe it will be easier to help!
– Ariel Serranoni
Jul 22 at 22:13
Thank you for your comment. I updated the post with my attempt.
– user3816
Jul 22 at 22:36
Thank you for your comment. I updated the post with my attempt.
– user3816
Jul 22 at 22:36
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Following the OP first note that $P=textconvv_i_i=1^k = textconva_i+b_i_i=1^k$. Now if $zin P=textconva_i+b_i_i=1^k,$ then $z$ can be written as a convex combination $z=sum_i lambda_i(a_i+b_i) = sum_i lambda_i a_i + sum_i lambda_i b_i in textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$. On the other hand if $zin textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$ then $z = sum_i lambda_i a_i +sum_j mu_j b_j = sum_i,jlambda_i mu_j(a_i+b_j) in textconva_i+b_i=P$, where $sum_i lambda_i=sum_j mu_j=1$, $lambda_i,mu_jgeq 0$.
We used convexity in the step that if $x_1,ldots, x_k subset A$ then $textconvx_1,ldots,x_k subset A$; similarly for $B$.
answered Jul 23 at 0:03
user3816
977
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Following the OP first note that $P=textconvv_i_i=1^k = textconva_i+b_i_i=1^k$. Now if $zin P=textconva_i+b_i_i=1^k,$ then $z$ can be written as a convex combination $z=sum_i lambda_i(a_i+b_i) = sum_i lambda_i a_i + sum_i lambda_i b_i in textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$. On the other hand if $zin textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$ then $z = sum_i lambda_i a_i +sum_j mu_j b_j = sum_i,jlambda_i mu_j(a_i+b_j) in textconva_i+b_i=P$, where $sum_i lambda_i=sum_j mu_j=1$, $lambda_i,mu_jgeq 0$.
We used convexity in the step that if $x_1,ldots, x_k subset A$ then $textconvx_1,ldots,x_k subset A$; similarly for $B$.
answered Jul 23 at 0:03
user3816
977
add a comment |Â
up vote
1
down vote
accepted
Following the OP first note that $P=textconvv_i_i=1^k = textconva_i+b_i_i=1^k$. Now if $zin P=textconva_i+b_i_i=1^k,$ then $z$ can be written as a convex combination $z=sum_i lambda_i(a_i+b_i) = sum_i lambda_i a_i + sum_i lambda_i b_i in textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$. On the other hand if $zin textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$ then $z = sum_i lambda_i a_i +sum_j mu_j b_j = sum_i,jlambda_i mu_j(a_i+b_j) in textconva_i+b_i=P$, where $sum_i lambda_i=sum_j mu_j=1$, $lambda_i,mu_jgeq 0$.
We used convexity in the step that if $x_1,ldots, x_k subset A$ then $textconvx_1,ldots,x_k subset A$; similarly for $B$.
answered Jul 23 at 0:03
user3816
977
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Following the OP first note that $P=textconvv_i_i=1^k = textconva_i+b_i_i=1^k$. Now if $zin P=textconva_i+b_i_i=1^k,$ then $z$ can be written as a convex combination $z=sum_i lambda_i(a_i+b_i) = sum_i lambda_i a_i + sum_i lambda_i b_i in textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$. On the other hand if $zin textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$ then $z = sum_i lambda_i a_i +sum_j mu_j b_j = sum_i,jlambda_i mu_j(a_i+b_j) in textconva_i+b_i=P$, where $sum_i lambda_i=sum_j mu_j=1$, $lambda_i,mu_jgeq 0$.
We used convexity in the step that if $x_1,ldots, x_k subset A$ then $textconvx_1,ldots,x_k subset A$; similarly for $B$.
answered Jul 23 at 0:03
user3816
977
Following the OP first note that $P=textconvv_i_i=1^k = textconva_i+b_i_i=1^k$. Now if $zin P=textconva_i+b_i_i=1^k,$ then $z$ can be written as a convex combination $z=sum_i lambda_i(a_i+b_i) = sum_i lambda_i a_i + sum_i lambda_i b_i in textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$. On the other hand if $zin textconva_i_i=1^k + textconvb_i_i=1^k=Q+R$ then $z = sum_i lambda_i a_i +sum_j mu_j b_j = sum_i,jlambda_i mu_j(a_i+b_j) in textconva_i+b_i=P$, where $sum_i lambda_i=sum_j mu_j=1$, $lambda_i,mu_jgeq 0$.
We used convexity in the step that if $x_1,ldots, x_k subset A$ then $textconvx_1,ldots,x_k subset A$; similarly for $B$.
answered Jul 23 at 0:03
user3816
977
edited Jul 23 at 0:09
answered Jul 23 at 0:03
user3816
977
answered Jul 23 at 0:03
user3816
977
answered Jul 23 at 0:03
user3816
977
977
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859813%2fpolytope-in-minkowski-sum%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
At first sight it seems true to me. Considering that $P$ is the convex hull of finitely many points in $A+B$ we could easily write any point in $P$ as the sum of points in two different convex hulls. Something like $p=sum_iin Ilambda_i(a_i + b_i)=sum_iin Ilambda_i a_i +sum_iin Ilambda_i b_i$ may work it out. If you have any attempt of your own maybe it will be easier to help!
– Ariel Serranoni
Jul 22 at 22:13
Thank you for your comment. I updated the post with my attempt.
– user3816
Jul 22 at 22:36