Mixing
Minkowski sum of polytopes from their facet normals and volumes
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
By Minkowski's work in the early 1900s, every polytope $Psubsetmathbb R^n$ is determined up to translation by its unit facet normals $u_1,dots,u_k$ and facet volumes $alpha_1,dots,alpha_k$. Associating to each polytope the set of normal vectors $N(P) = alpha_i u_i$ this describes a bijection between polytopes up to translation and balanced vector configurations. (This generalizes to a bijection between convex bodies up to translation and their surface measures.)
When $n=2$ and $P,Qsubsetmathbb R^2$ are polytopes, the set $N(P+Q)$ associated to the Minkowski sum is the union $N(P)cup N(Q)$ with vectors in the same direction added together. (The sum of the surface measures.)
For $n>2$ these are two different operations: the union of the vector configurations with vectors in the same direction summed up defines the Blaschke sum $P # Q$.
Is any description of $N(P+Q)$ in terms of $N(P)$ and $N(Q)$ known for $n>2$?
measure-theory convex-polytopes convex-geometry sumsets
edited 2 hours ago
Martin Sleziak
2,86932028
asked 4 hours ago
Christoph
1936
add a comment |Â
up vote
2
down vote
favorite
By Minkowski's work in the early 1900s, every polytope $Psubsetmathbb R^n$ is determined up to translation by its unit facet normals $u_1,dots,u_k$ and facet volumes $alpha_1,dots,alpha_k$. Associating to each polytope the set of normal vectors $N(P) = alpha_i u_i$ this describes a bijection between polytopes up to translation and balanced vector configurations. (This generalizes to a bijection between convex bodies up to translation and their surface measures.)
When $n=2$ and $P,Qsubsetmathbb R^2$ are polytopes, the set $N(P+Q)$ associated to the Minkowski sum is the union $N(P)cup N(Q)$ with vectors in the same direction added together. (The sum of the surface measures.)
For $n>2$ these are two different operations: the union of the vector configurations with vectors in the same direction summed up defines the Blaschke sum $P # Q$.
Is any description of $N(P+Q)$ in terms of $N(P)$ and $N(Q)$ known for $n>2$?
measure-theory convex-polytopes convex-geometry sumsets
edited 2 hours ago
Martin Sleziak
2,86932028
asked 4 hours ago
Christoph
1936
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
By Minkowski's work in the early 1900s, every polytope $Psubsetmathbb R^n$ is determined up to translation by its unit facet normals $u_1,dots,u_k$ and facet volumes $alpha_1,dots,alpha_k$. Associating to each polytope the set of normal vectors $N(P) = alpha_i u_i$ this describes a bijection between polytopes up to translation and balanced vector configurations. (This generalizes to a bijection between convex bodies up to translation and their surface measures.)
When $n=2$ and $P,Qsubsetmathbb R^2$ are polytopes, the set $N(P+Q)$ associated to the Minkowski sum is the union $N(P)cup N(Q)$ with vectors in the same direction added together. (The sum of the surface measures.)
For $n>2$ these are two different operations: the union of the vector configurations with vectors in the same direction summed up defines the Blaschke sum $P # Q$.
Is any description of $N(P+Q)$ in terms of $N(P)$ and $N(Q)$ known for $n>2$?
measure-theory convex-polytopes convex-geometry sumsets
edited 2 hours ago
Martin Sleziak
2,86932028
asked 4 hours ago
Christoph
1936
By Minkowski's work in the early 1900s, every polytope $Psubsetmathbb R^n$ is determined up to translation by its unit facet normals $u_1,dots,u_k$ and facet volumes $alpha_1,dots,alpha_k$. Associating to each polytope the set of normal vectors $N(P) = alpha_i u_i$ this describes a bijection between polytopes up to translation and balanced vector configurations. (This generalizes to a bijection between convex bodies up to translation and their surface measures.)
When $n=2$ and $P,Qsubsetmathbb R^2$ are polytopes, the set $N(P+Q)$ associated to the Minkowski sum is the union $N(P)cup N(Q)$ with vectors in the same direction added together. (The sum of the surface measures.)
For $n>2$ these are two different operations: the union of the vector configurations with vectors in the same direction summed up defines the Blaschke sum $P # Q$.
Is any description of $N(P+Q)$ in terms of $N(P)$ and $N(Q)$ known for $n>2$?
measure-theory convex-polytopes convex-geometry sumsets
measure-theory convex-polytopes convex-geometry sumsets
edited 2 hours ago
Martin Sleziak
2,86932028
asked 4 hours ago
Christoph
1936
edited 2 hours ago
Martin Sleziak
2,86932028
asked 4 hours ago
Christoph
1936
edited 2 hours ago
Martin Sleziak
2,86932028
edited 2 hours ago
Martin Sleziak
2,86932028
edited 2 hours ago
Martin Sleziak
2,86932028
2,86932028
asked 4 hours ago
Christoph
1936
asked 4 hours ago
Christoph
1936
asked 4 hours ago
Christoph
1936
1936
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
There is no simple description.
A face of the Minkowski sum is the Minkowski sum of faces of the summands. More exactly, if $F_u(P)$ denotes the face of $P$ with outer normal $u$, then
$$
F_u(P+Q) = F_u(P) + F_u(Q).
$$
In dimension $2$ this yields the description that you gave. In higher dimensions it can happen that $F_u(P+Q)$ is a facet while $F_u(P)$ and $F_u(Q)$ are faces of smaller dimensions. (Take for example the octahedron and perturb its support numbers in two different ways; the Minkowski sum of these two polytopes might have more than eight faces: new faces will be parallel to the "equators" of the octahedron.)
The normal fan of the Minkowski sum is the coarsest common refinement of the normal fans of the summands. Thus, in order to know the normals to the facets of $P+Q$ you need to know the face structures of $P$ and $Q$, which is not easy to read off the facet volumes $alpha_i$, $beta_i$.
Even if you know the normals to the facets, it is not easy to determine the facet volumes (you need to compute the volume of a Minkowski sum). This is not easy already in the combinatorially simplest case, when the face structures (the normal fans) of $P$ and $Q$ are the same.
answered 2 hours ago
Ivan Izmestiev
3,6181237
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
There is no simple description.
A face of the Minkowski sum is the Minkowski sum of faces of the summands. More exactly, if $F_u(P)$ denotes the face of $P$ with outer normal $u$, then
$$
F_u(P+Q) = F_u(P) + F_u(Q).
$$
In dimension $2$ this yields the description that you gave. In higher dimensions it can happen that $F_u(P+Q)$ is a facet while $F_u(P)$ and $F_u(Q)$ are faces of smaller dimensions. (Take for example the octahedron and perturb its support numbers in two different ways; the Minkowski sum of these two polytopes might have more than eight faces: new faces will be parallel to the "equators" of the octahedron.)
The normal fan of the Minkowski sum is the coarsest common refinement of the normal fans of the summands. Thus, in order to know the normals to the facets of $P+Q$ you need to know the face structures of $P$ and $Q$, which is not easy to read off the facet volumes $alpha_i$, $beta_i$.
Even if you know the normals to the facets, it is not easy to determine the facet volumes (you need to compute the volume of a Minkowski sum). This is not easy already in the combinatorially simplest case, when the face structures (the normal fans) of $P$ and $Q$ are the same.
answered 2 hours ago
Ivan Izmestiev
3,6181237
add a comment |Â
up vote
4
down vote
There is no simple description.
A face of the Minkowski sum is the Minkowski sum of faces of the summands. More exactly, if $F_u(P)$ denotes the face of $P$ with outer normal $u$, then
$$
F_u(P+Q) = F_u(P) + F_u(Q).
$$
In dimension $2$ this yields the description that you gave. In higher dimensions it can happen that $F_u(P+Q)$ is a facet while $F_u(P)$ and $F_u(Q)$ are faces of smaller dimensions. (Take for example the octahedron and perturb its support numbers in two different ways; the Minkowski sum of these two polytopes might have more than eight faces: new faces will be parallel to the "equators" of the octahedron.)
The normal fan of the Minkowski sum is the coarsest common refinement of the normal fans of the summands. Thus, in order to know the normals to the facets of $P+Q$ you need to know the face structures of $P$ and $Q$, which is not easy to read off the facet volumes $alpha_i$, $beta_i$.
Even if you know the normals to the facets, it is not easy to determine the facet volumes (you need to compute the volume of a Minkowski sum). This is not easy already in the combinatorially simplest case, when the face structures (the normal fans) of $P$ and $Q$ are the same.
answered 2 hours ago
Ivan Izmestiev
3,6181237
add a comment |Â
up vote
4
down vote
up vote
4
down vote
There is no simple description.
A face of the Minkowski sum is the Minkowski sum of faces of the summands. More exactly, if $F_u(P)$ denotes the face of $P$ with outer normal $u$, then
$$
F_u(P+Q) = F_u(P) + F_u(Q).
$$
In dimension $2$ this yields the description that you gave. In higher dimensions it can happen that $F_u(P+Q)$ is a facet while $F_u(P)$ and $F_u(Q)$ are faces of smaller dimensions. (Take for example the octahedron and perturb its support numbers in two different ways; the Minkowski sum of these two polytopes might have more than eight faces: new faces will be parallel to the "equators" of the octahedron.)
The normal fan of the Minkowski sum is the coarsest common refinement of the normal fans of the summands. Thus, in order to know the normals to the facets of $P+Q$ you need to know the face structures of $P$ and $Q$, which is not easy to read off the facet volumes $alpha_i$, $beta_i$.
Even if you know the normals to the facets, it is not easy to determine the facet volumes (you need to compute the volume of a Minkowski sum). This is not easy already in the combinatorially simplest case, when the face structures (the normal fans) of $P$ and $Q$ are the same.
answered 2 hours ago
Ivan Izmestiev
3,6181237
There is no simple description.
A face of the Minkowski sum is the Minkowski sum of faces of the summands. More exactly, if $F_u(P)$ denotes the face of $P$ with outer normal $u$, then
$$
F_u(P+Q) = F_u(P) + F_u(Q).
$$
In dimension $2$ this yields the description that you gave. In higher dimensions it can happen that $F_u(P+Q)$ is a facet while $F_u(P)$ and $F_u(Q)$ are faces of smaller dimensions. (Take for example the octahedron and perturb its support numbers in two different ways; the Minkowski sum of these two polytopes might have more than eight faces: new faces will be parallel to the "equators" of the octahedron.)
The normal fan of the Minkowski sum is the coarsest common refinement of the normal fans of the summands. Thus, in order to know the normals to the facets of $P+Q$ you need to know the face structures of $P$ and $Q$, which is not easy to read off the facet volumes $alpha_i$, $beta_i$.
Even if you know the normals to the facets, it is not easy to determine the facet volumes (you need to compute the volume of a Minkowski sum). This is not easy already in the combinatorially simplest case, when the face structures (the normal fans) of $P$ and $Q$ are the same.
answered 2 hours ago
Ivan Izmestiev
3,6181237
edited 51 mins ago
answered 2 hours ago
Ivan Izmestiev
3,6181237
answered 2 hours ago
Ivan Izmestiev
3,6181237
answered 2 hours ago
Ivan Izmestiev
3,6181237
3,6181237
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%2fmathoverflow.net%2fquestions%2f314399%2fminkowski-sum-of-polytopes-from-their-facet-normals-and-volumes%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
