<p>Lattices and linear subspaces are closed under Minkowski sum. Thats more or less immediate from their definition. Lattices+linear subspaces are closed under Minkowski sum (i.e., a member of this set is for example a set of parallel lines in distance 1 from each other). Connected polygons with holes are closed under Minkowski sum. Rings [the set differences of two concentric disks] are closed under Minkowski sum (a disk is considered to be a ring, naturally). The set of line segments parallel to a certain direction are closed under Minkowski sum. Mushed potatoes are closed under Minkowski sum, but only if they are well cooked (or maybe not, it is too late)...</p>

<p>Also, the family of finite union of concentric rings is closed under Minkowski sum. </p>

CC BY-SA 2.5
2011-03-02T05:15:43.340Z
2011-03-02T16:56:51.607Z
2011-03-02T16:56:51.607Z
Sariel Har-Peled
<p>The Minkowski sum of two sets of vectors $A, B \in R^d$ is given by </p>

<p>$$ A \oplus B  = \{ a + b \mid a \in A, b \in B \}$$</p>

<p>I just heard an interesting problem (attributed to Dan Halperin): Given a shape $B$, does there exist a shape $A$ such that $A \oplus A = B$ ?</p>

<p>But that's not my question (it appears to be an open problem). Observe that in the above problem, if $B$ is a convex set, then there exists a solution $A = (1/2)B$ since convex sets are closed under the taking of Minkowski sums. </p>

<p>Fix a class of shapes ${\cal S}$. We say that ${\cal S}$ is <em>closed</em> under Minkowski sums if for any $A, B \in {\cal S}, A \oplus B \in {\cal S}$. </p>

<p>So my question is:</p>

<blockquote>
  <p>Is there a nice characterization of
  classes of shapes ${\cal S}$ that are
  closed under Minkowski sums ?</p>
</blockquote>

CC BY-SA 2.5
2011-03-01T21:49:58.160Z
I read the revision 2.  (1) I fail to see how “convex sets are closed under taking Minkowski sums” is the reason for “there exists a solution A=(1/2)B” (although both facts are clear).  (2) I doubt that there is any equivalent characterization nicer than “closed under Minkowski sums.”
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-01T23:04:49.117Z
It's true that there isn't a direct implication. But the proof uses the fact that the sum of two convex sets is convex. I could reword to say "also note that.." instead of "since..."
Suresh Venkat
CC BY-SA 2.5
2011-03-01T23:15:46.137Z
I do not think that we use the fact that the Minkowski sum of two convex sets is convex when proving (B/2)⊕(B/2)=B for a convex set B.  The containment (B/2)⊕(B/2)⊇B has nothing to do with convexity.  The containment (B/2)⊕(B/2)⊆B follows from the fact that B is convex: for any x,y∈B, (x/2)+(y/2)∈B because of the convexity of B.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-02T00:05:28.860Z
true. good point. I had another proof in mind but you're right that you don't need it
Suresh Venkat
CC BY-SA 2.5
2011-03-02T06:29:58.170Z
I wonder if it's possible to argue the difficulty of having a nice characterization from some known hardness results, like deciding if a given set of vectors form a Hilbert basis (http://dx.doi.org/10.1007/s10107-009-0294-5), or computing the Frobenius number of a given set of integers (http://dx.doi.org/10.1007/BF01300131), even when each "shape" is a point.  I didn't succeed yet, or maybe this is a wrong approach.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-02T17:14:15.457Z
@Yoshio: it's possible. This question could also be related to 'sumset' work in general groups as well.
Suresh Venkat
<cg.comp-geom>
Closure under Minkowski sum.
Suresh Venkat
# Closure under Minkowski sum.

(Asked by: username_0 on 2011-03-01)

The Minkowski sum of two sets of vectors $A, B \in R^d$ is given by

$$ A \oplus B = \{ a + b \mid a \in A, b \in B \}$$

I just heard an interesting problem (attributed to Dan Halperin): Given a shape $B$, does there exist a shape $A$ such that $A \oplus A = B$ ?

But that's not my question (it appears to be an open problem). Observe that in the above problem, if $B$ is a convex set, then there exists a solution $A = (1/2)B$ since convex sets are closed under the taking of Minkowski sums.

Fix a class of shapes ${\cal S}$. We say that ${\cal S}$ is *closed* under Minkowski sums if for any $A, B \in {\cal S}, A \oplus B \in {\cal S}$.

So my question is:

> Is there a nice characterization of
> classes of shapes ${\cal S}$ that are
> closed under Minkowski sums ?

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: I read the revision 2.  (1) I fail to see how “convex sets are closed under taking Minkowski sums” is the reason for “there exists a solution A=(1/2)B” (although both facts are clear).  (2) I doubt that there is any equivalent characterization nicer than “closed under Minkowski sums.”  
> **username_0**: It's true that there isn't a direct implication. But the proof uses the fact that the sum of two convex sets is convex. I could reword to say "also note that.." instead of "since..."  
> **username_1**: I do not think that we use the fact that the Minkowski sum of two convex sets is convex when proving (B/2)⊕(B/2)=B for a convex set B.  The containment (B/2)⊕(B/2)⊇B has nothing to do with convexity.  The containment (B/2)⊕(B/2)⊆B follows from the fact that B is convex: for any x,y∈B, (x/2)+(y/2)∈B because of the convexity of B.  
> **username_0**: true. good point. I had another proof in mind but you're right that you don't need it  
> **username_2**: I wonder if it's possible to argue the difficulty of having a nice characterization from some known hardness results, like deciding if a given set of vectors form a Hilbert basis (http://dx.doi.org/10.1007/s10107-009-0294-5), or computing the Frobenius number of a given set of integers (http://dx.doi.org/10.1007/BF01300131), even when each "shape" is a point.  I didn't succeed yet, or maybe this is a wrong approach.  
> **username_0**: @Yoshio: it's possible. This question could also be related to 'sumset' work in general groups as well.  

---

## 1 answers

### Answer by username_3 on 2011-03-02. Score: 6 | Accepted answer

Lattices and linear subspaces are closed under Minkowski sum. Thats more or less immediate from their definition. Lattices+linear subspaces are closed under Minkowski sum (i.e., a member of this set is for example a set of parallel lines in distance 1 from each other). Connected polygons with holes are closed under Minkowski sum. Rings [the set differences of two concentric disks] are closed under Minkowski sum (a disk is considered to be a ring, naturally). The set of line segments parallel to a certain direction are closed under Minkowski sum. Mushed potatoes are closed under Minkowski sum, but only if they are well cooked (or maybe not, it is too late)...

Also, the family of finite union of concentric rings is closed under Minkowski sum.


---

