Namespaces
Variants
Actions

Difference between revisions of "Minkowski addition"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 40 formulas out of 40 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
The Minkowski sum of two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202101.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202102.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202103.png" />-dimensional Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202104.png" /> is defined as the set
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,  
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202105.png" /></td> </tr></table>
+
Out of 40 formulas, 40 were replaced by TEX code.-->
  
one also defines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202106.png" /> for real <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202107.png" />. Coupled with the notion of [[Volume|volume]], this Minkowski addition leads to the [[Brunn–Minkowski theorem|Brunn–Minkowski theorem]] and is the basis for the Brunn–Minkowski theory of convex bodies (i.e., compact convex sets).
+
{{TEX|semi-auto}}{{TEX|done}}
 +
The Minkowski sum of two sets $A$, $B$ in $n$-dimensional Euclidean space $\mathbf{E} ^ { n }$ is defined as the set
 +
 
 +
\begin{equation*} A + B : = \{ a + b : a \in A , b \in B \}; \end{equation*}
 +
 
 +
one also defines $\lambda A : = \{ \lambda a : a \in A \}$ for real $\lambda &gt; 0$. Coupled with the notion of [[Volume|volume]], this Minkowski addition leads to the [[Brunn–Minkowski theorem|Brunn–Minkowski theorem]] and is the basis for the Brunn–Minkowski theory of convex bodies (i.e., compact convex sets).
  
 
Repeated Minkowski addition of compact sets has a convexifying effect; this is made precise by the Shapley–Folkman–Starr theorem.
 
Repeated Minkowski addition of compact sets has a convexifying effect; this is made precise by the Shapley–Folkman–Starr theorem.
  
The structure of Minkowski addition is well studied on the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202108.png" /> of convex bodies in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m1202109.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021010.png" /> with Minkowski addition and multiplication by non-negative scalars is a convex cone. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021011.png" />, where
+
The structure of Minkowski addition is well studied on the space $\mathcal{K} ^ { n }$ of convex bodies in $\mathbf{E} ^ { n }$. $\mathcal{K} ^ { n }$ with Minkowski addition and multiplication by non-negative scalars is a convex cone. The mapping $K \mapsto h _ { K }$, where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021012.png" /></td> </tr></table>
+
\begin{equation*} h _ { K } ( u ) : = \operatorname { max } \{ \langle x , u \rangle : x \in K \}, \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021013.png" /></td> </tr></table>
+
\begin{equation*} u \in S ^ { n - 1 } : = \{ v \in {\bf E} : \langle v , v \rangle = 1 \} \end{equation*}
  
(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021014.png" /> being the scalar product) is the support function, maps this cone isomorphically into the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021015.png" /> of continuous real functions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021016.png" />. The image is precisely the closed convex cone of restrictions of sublinear functions. (For corresponding results in topological vector spaces, see [[#References|[a2]]] and its bibliography.)
+
($\langle \, .\, ,\,  . \, \rangle$ being the scalar product) is the support function, maps this cone isomorphically into the space $C ( S ^ { n - 1 } )$ of continuous real functions on $S ^ { n - 1 }$. The image is precisely the closed convex cone of restrictions of sublinear functions. (For corresponding results in topological vector spaces, see [[#References|[a2]]] and its bibliography.)
  
For convex bodies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021017.png" />, the body <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021018.png" /> is called a summand of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021019.png" /> if there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021020.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021021.png" />. Each summand of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021022.png" /> is a non-empty intersection of a family of translates of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021023.png" />; the converse is true for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021024.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021025.png" /> is called indecomposable if every summand of K is of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021026.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021028.png" />. In the plane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021029.png" />, the indecomposable convex bodies are precisely the segments and the triangles. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021030.png" />, every simplicial convex polytope in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021031.png" /> is indecomposable, hence most convex bodies (in the Baire category sense, cf. also [[Baire set|Baire set]]) are indecomposable.
+
For convex bodies $K , L \in {\cal K} ^ { n }$, the body $L$ is called a summand of $K$ if there exists an $M \in \mathcal{K} ^ { n }$ such that $K = L + M$. Each summand of $K$ is a non-empty intersection of a family of translates of $K$; the converse is true for $n = 2$. $K$ is called indecomposable if every summand of K is of the form $\lambda K + t$ with $\lambda &gt; 0$ and $t \in \mathbf{E} ^ { n }$. In the plane $\mathbf{E} ^ { 2 }$, the indecomposable convex bodies are precisely the segments and the triangles. For $n \geq 3$, every simplicial convex polytope in $\mathbf{E} ^ { n }$ is indecomposable, hence most convex bodies (in the Baire category sense, cf. also [[Baire set|Baire set]]) are indecomposable.
  
A mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021032.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021033.png" /> into an Abelian group is called Minkowski additive if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021034.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021035.png" />. Such mappings are special valuations and play a particular role in the investigation of valuations on convex bodies. Common examples are the mean width and the Steiner point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021036.png" />. A surjective mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021037.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021038.png" /> that commutes with rigid motions and is continuous with respect to the [[Hausdorff metric|Hausdorff metric]] is trivial, namely of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021039.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120210/m12021040.png" />.
+
A mapping $\phi$ from $\mathcal{K} ^ { n }$ into an Abelian group is called Minkowski additive if $\phi ( K + L ) = \phi ( K ) + \phi ( L )$ for all $K , L \in {\cal K} ^ { n }$. Such mappings are special valuations and play a particular role in the investigation of valuations on convex bodies. Common examples are the mean width and the Steiner point $s$. A surjective mapping $\psi : \mathcal{K} ^ { n } \rightarrow \mathcal{K} ^ { n }$ with $\psi ( K + L ) = \psi ( K ) + \psi ( L )$ that commutes with rigid motions and is continuous with respect to the [[Hausdorff metric|Hausdorff metric]] is trivial, namely of the form $\psi ( K ) = \lambda [ K - s ( K ) ] + s ( K )$ with $\lambda \neq 0$.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Schneider,  "Convex bodies: the Brunn–Minkowski theory" , Cambridge Univ. Press  (1993)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Urbanski,  "A generalization of the Minkowski–Rådström–Hörmander theorem"  ''Bull. Acad. Polon. Sci. Ser. Sci. Math., Astr., Phys.'' , '''24'''  (1976)  pp. 709 – 715</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  R. Schneider,  "Convex bodies: the Brunn–Minkowski theory" , Cambridge Univ. Press  (1993)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  R. Urbanski,  "A generalization of the Minkowski–Rådström–Hörmander theorem"  ''Bull. Acad. Polon. Sci. Ser. Sci. Math., Astr., Phys.'' , '''24'''  (1976)  pp. 709 – 715</td></tr></table>

Latest revision as of 15:30, 1 July 2020

The Minkowski sum of two sets $A$, $B$ in $n$-dimensional Euclidean space $\mathbf{E} ^ { n }$ is defined as the set

\begin{equation*} A + B : = \{ a + b : a \in A , b \in B \}; \end{equation*}

one also defines $\lambda A : = \{ \lambda a : a \in A \}$ for real $\lambda > 0$. Coupled with the notion of volume, this Minkowski addition leads to the Brunn–Minkowski theorem and is the basis for the Brunn–Minkowski theory of convex bodies (i.e., compact convex sets).

Repeated Minkowski addition of compact sets has a convexifying effect; this is made precise by the Shapley–Folkman–Starr theorem.

The structure of Minkowski addition is well studied on the space $\mathcal{K} ^ { n }$ of convex bodies in $\mathbf{E} ^ { n }$. $\mathcal{K} ^ { n }$ with Minkowski addition and multiplication by non-negative scalars is a convex cone. The mapping $K \mapsto h _ { K }$, where

\begin{equation*} h _ { K } ( u ) : = \operatorname { max } \{ \langle x , u \rangle : x \in K \}, \end{equation*}

\begin{equation*} u \in S ^ { n - 1 } : = \{ v \in {\bf E} : \langle v , v \rangle = 1 \} \end{equation*}

($\langle \, .\, ,\, . \, \rangle$ being the scalar product) is the support function, maps this cone isomorphically into the space $C ( S ^ { n - 1 } )$ of continuous real functions on $S ^ { n - 1 }$. The image is precisely the closed convex cone of restrictions of sublinear functions. (For corresponding results in topological vector spaces, see [a2] and its bibliography.)

For convex bodies $K , L \in {\cal K} ^ { n }$, the body $L$ is called a summand of $K$ if there exists an $M \in \mathcal{K} ^ { n }$ such that $K = L + M$. Each summand of $K$ is a non-empty intersection of a family of translates of $K$; the converse is true for $n = 2$. $K$ is called indecomposable if every summand of K is of the form $\lambda K + t$ with $\lambda > 0$ and $t \in \mathbf{E} ^ { n }$. In the plane $\mathbf{E} ^ { 2 }$, the indecomposable convex bodies are precisely the segments and the triangles. For $n \geq 3$, every simplicial convex polytope in $\mathbf{E} ^ { n }$ is indecomposable, hence most convex bodies (in the Baire category sense, cf. also Baire set) are indecomposable.

A mapping $\phi$ from $\mathcal{K} ^ { n }$ into an Abelian group is called Minkowski additive if $\phi ( K + L ) = \phi ( K ) + \phi ( L )$ for all $K , L \in {\cal K} ^ { n }$. Such mappings are special valuations and play a particular role in the investigation of valuations on convex bodies. Common examples are the mean width and the Steiner point $s$. A surjective mapping $\psi : \mathcal{K} ^ { n } \rightarrow \mathcal{K} ^ { n }$ with $\psi ( K + L ) = \psi ( K ) + \psi ( L )$ that commutes with rigid motions and is continuous with respect to the Hausdorff metric is trivial, namely of the form $\psi ( K ) = \lambda [ K - s ( K ) ] + s ( K )$ with $\lambda \neq 0$.

References

[a1] R. Schneider, "Convex bodies: the Brunn–Minkowski theory" , Cambridge Univ. Press (1993)
[a2] R. Urbanski, "A generalization of the Minkowski–Rådström–Hörmander theorem" Bull. Acad. Polon. Sci. Ser. Sci. Math., Astr., Phys. , 24 (1976) pp. 709 – 715
How to Cite This Entry:
Minkowski addition. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Minkowski_addition&oldid=49911
This article was adapted from an original article by Rolf Schneider (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article