2
$\begingroup$

I'd like to show (or disprove) the claim that the Minkowski sum of two triangles with vertices in $\mathbb{R}^3$, $A+B$, is equal to the union of the unions of the Minkowski sums of $A$ along all edges of $B$ and the $B$ along all edges of $A$:

$ A + B = \cup \left[ \cup_{e \in B}\ A + e\ ,\ \cup_{e \in A}\ B + e \right] =: C $

where $e \in A$ denotes an edge-segment $e$ on the boundary of $A$.

I believe it's enough to show that $C$ is convex.

$\endgroup$
  • $\begingroup$ Where does this come from? $\endgroup$ – Igor Rivin Dec 29 '15 at 18:51
  • $\begingroup$ I had implemented an algorithm to construct the Minkowski sum of a triangle + a segment and wanted to know if I could trivially extend it to a triangle + a triangle (though surely this is not an efficient way). $\endgroup$ – Alec Jacobson Dec 29 '15 at 21:53
3
$\begingroup$

Here is a crude way to see that this is true: Given $a$ and $b$ in the interiors of $A$ and $B$, respectively, consider $A-a =\{x-a | x\in A\}$ and $b-B =\{b-y | y\in B\}$. These shifted triangles have a convex intersection that is more than a point because $2+2 \gt 3$ so the tangent spaces have nontrivial intersection. The intersection $\{x-a=b-y\}$ gives the pairs of points $\{(x,y) | x+y=a+b\}$ adding up to $a+b$. Each extreme point of the intersection corresponds to an extreme point of $A$ or $B$, hence a point contained in an edge of $A$ or an edge of $B$.

This argument only used that $A$ and $B$ are convex, so the same argument works for other convex $2$-dimensional shapes in $\mathbb{R}^3$, or $d$-dimensional shapes in $\mathbb{R}^{2d-1}.$

There is a nicer version of this argument in terms of the map from $A \times B$ to the Minkowski sum. The preimage of a point must intersect the $3$-skeleton which consists of $(A\times \delta B) \cup (\delta A \times B).$

$\endgroup$
  • $\begingroup$ Minor note, if a = b to begin with then the intersection of the shifted triangles might be just a point. $\endgroup$ – Alec Jacobson Dec 30 '15 at 17:02
  • $\begingroup$ I think it's not that $a=b$ that could cause that, it is that $a$ or $b$ could be on the boundary of $A$ or $B$, but that case is trivial since then the point is already obviously in an edge+triangle. $\endgroup$ – Douglas Zare Dec 31 '15 at 2:13
3
$\begingroup$

Let $a_i$ and $b_j$ be the vertices of the triangles. For a given point $p$ in $A+B$ the space of solutions $(\alpha_1,\ldots,\beta_3)$ to $$ p = \sum_i \alpha_i a_i + \sum_j \beta_j b_j, ~\sum_i \alpha_i=1, \sum_j \beta_j = 1, \alpha_i\geq 0,\beta_i\geq 0 $$ is a nonempty convex polytope. Since it is given by $5$ equations and some inequalities, and lies in dimension $6$, at a vertex of it one of the inequalities must be an equality. Thus for any $p$ you can write it is as an aforementioned linear combination with either one of $\alpha_i$ or one of $\beta_j$ equal to zero.

This is precisely equivalent to the claim you seek.

$\endgroup$
3
$\begingroup$

By far the simplest argument is given by Jack Huizenga here. One line summary: Minkowski sum and convex hulls commute.

$\endgroup$
0
$\begingroup$

Let $u_1,u_2$ be vectors determined by two edges of $A$, and $v_1,v_2$ vectors determined by two edges of $B$. Let $U$ be the (linear) span of $\{u_1,u_2\}$ and $V$ the span of $\{v_1,v_2\}$. Both $U$ and $V$ have dimension $2$, so they intersect in a subspace $W$ of dimension at least $1$. Let $w$ be a unit vector in $W$.

Now if $a$ is a point from the relative interior of $A$, and $b$ a point from the relative interior of $B$, then for a sufficiently small $\varepsilon>0$, we have $a':=a+\varepsilon w \in A$, $b':=b-\varepsilon w \in B$, and $a'+b'=a+b$. Thus we can select $\varepsilon$ so that either $a'$ is on the relative boundary of $A$ or $b'$ is on the relative boundary of $B$. So, indeed, $A+B=C$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.