集合のミンコフスキー和
ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)が与えられたとき、\(A_{1}\)の点と\(A_{2}\)の点のベクトル和をすべて集めてできる集合を、\begin{equation*}A_{1}+A_{2}=\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\}
\end{equation*}で表記し、これを\(A_{1}\)と\(A_{2}\)のミンコフスキー和（Minkowski sum）や和（sum）などと呼びます。
\right\} \\
A_{2} &=&\left\{ \left( 0,0\right) ,\left( 1,1\right) ,\left( 1,-1\right)
\right\}
\end{eqnarray*}が与えられたとき、\begin{equation*}
A_{1}+A_{2}=\left\{ \left( 1,0\right) ,\left( 2,1\right) ,\left( 2,-1\right)
,\left( 0,1\right) ,\left( 1,2\right) ,\left( 0,-1\right) ,\left(
1,-2\right) \right\}
\end{equation*}となります。
\end{equation*}で表記し、奇数集合を、\begin{equation*}
O=\left\{ \cdots ,-3,-1,1,3,\cdots \right\}
\end{equation*}で表記するとき、偶数と奇数の和は奇数であることを踏まえると、\begin{equation*}
E+O=O
\end{equation*}となります。
\end{equation*}が成り立ちます（演習問題）。
\end{equation*}という表記を採用します。つまり、\begin{equation*}
a+A=\left\{ a+x\in \mathbb{R} ^{n}\ |\ x\in A\right\}
\end{equation*}です。特に、点\(a\)がゼロベクトルである場合には、\begin{eqnarray*}0+A &=&\left\{ 0+x\in \mathbb{R} ^{n}\ |\ x\in A\right\} \\
&=&\left\{ x\in \mathbb{R} ^{n}\ |\ x\in A\right\} \\
&=&A
\end{eqnarray*}となります。
\end{equation*}で表記し、これを\(A_{1}\)と\(A_{2}\)のミンコフスキー差（Minkowski difference）や差（difference）などと呼びます。集合のスカラー倍の定義より、\begin{equation}-A_{2}=\left\{ -x_{2}\in \mathbb{R} ^{n}\ |\ x_{2}\in A_{2}\right\} \quad \cdots (1)
\end{equation}となるため、\begin{eqnarray*}
A_{1}-A_{2} &=&\left\{ x_{1}-x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\} \quad \because \text{ミンコフスキー差の定義} \\
&=&\left\{ x_{1}+\left( -x_{2}\right) \in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\} \\
&=&\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in -A_{2}\right\} \quad \because \left(
1\right) \\
&=&A_{1}+\left( -A_{2}\right) \quad \because \text{ミンコフスキー和の定義}
\end{eqnarray*}すなわち、\begin{equation*}
A_{1}-A_{2}=A_{1}+\left( -A_{2}\right)
\end{equation*}を得ます。つまり、ミンコフスキー差\(A_{1}-A_{2}\)は集合\(A_{1}\)と集合\(A_{2}\)のスカラー\(-1\)倍のミンコフスキー和として理解できます。
ミンコワスキー和の幾何学的解釈
\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)が与えられたとき、それらのミンコフスキー和\(A_{1}+A_{2}\)を視覚的に理解するためには、まず一方の集合の要素\(x_{1}\in A_{1}\)を任意に選んだ上で、それともう一方の集合\(A_{2}\)のミンコワスキー和\begin{equation}x_{1}+A_{2}=\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{2}\in A_{2}\right\} \quad \cdots (1)
\end{equation}をとります。\(A_{1}\)のそれぞれの要素\(x_{1}\)について上の集合をとれば\(\mathbb{R} ^{n}\)の部分集合族\(\left\{x_{1}+A_{2}\right\} _{x_{1}\in A_{1}}\)が得られるため、その和集合をとると、\begin{eqnarray*}\bigcup\limits_{x_{1}\in A_{1}}\left( x_{1}+A_{2}\right)
&=&\bigcup\limits_{x_{1}\in A_{1}}\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{2}\in A_{2}\right\} \quad \because \left( 1\right) \\
&=&\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\} \\
&=&A_{1}+A_{2}
\end{eqnarray*}となり、そもそものミンコフスキー和\(A_{1}+A_{2}\)が得られます。このように分割して考えることにより、ミンコワスキー和を視覚的に理解しやすくなります。
\end{equation*}で与えられているものとします。これは原点を中心とする半径\(1\)の円です。このとき、以下のミンコワスキー和\begin{equation*}A+\mathbb{R} _{+}^{2}
\end{equation*}はどのような図形になるのでしょうか。円上の点\(\left( x_{1},y_{1}\right) \in A\)を任意に選んだとき、これと\(\mathbb{R} _{+}^{2}\)のミンコワスキー和は、\begin{equation*}\left( x_{1},y_{1}\right) +\mathbb{R} _{+}^{2}=\left\{ \left( x_{1}+x_{2},y_{1}+y_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{2}\geq 0\wedge y_{2}\geq 0\right\}
\end{equation*}となりますが、これは下図のグレーの領域として描かれます。
円\(A\)上の他の点についても同様に考えた上で、得られた集合の和集合をとると\(A+\mathbb{R} _{+}^{2}\)が得られますが、これは下図のグレーの領域として描かれます。
2つの凸集合のミンコフスキー和は凸集合
\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)がともに凸集合である場合、それらのミンコスキー和\(A_{1}+A_{2}\)もまた凸集合になることが保証されます。
\end{equation*}という関係が成り立ちます。\(A_{1}\)と\(A_{2}\)がともに凸集合であるものとします。\(-A_{2}\)は凸集合のスカラー\(-1\)倍であるため凸集合です。したがって、\(A_{1}+\left(-A_{2}\right) \)は凸集合どうしのミンコフスキー和であるため先の命題よりこれは凸集合であり、それと等しい\(A_{1}-A_{2}\)もまた凸集合です。つまり、凸集合どうしのミンコフスキー差もまた凸集合であるということです。
\left( c,d\right) &=&\left\{ x\in \mathbb{R} \ |\ c<x<d\right\}
\end{eqnarray*}をとります。これらはともに\(\mathbb{R} \)上の凸集合であるため、これらのミンコフスキー和とミンコフスキー差はともに凸集合です。実際、ミンコフスキー和は、\begin{eqnarray*}\left( a,b\right) +\left( c,d\right) &=&\left\{ x+y\in \mathbb{R} \ |\ a<x<b\wedge c<y<d\right\} \\
&=&\left( a+c,b+d\right)
\end{eqnarray*}となりますが、これは有界開区間であるため凸集合です。一方、ミンコフスキー差は、\begin{eqnarray*}
\left( a,b\right) -\left( c,d\right) &=&\left\{ x-y\in \mathbb{R} \ |\ a<x<b\wedge c<y<d\right\} \\
&=&\left( a-d,b-c\right)
\end{eqnarray*}となりますが、これも有界開区間であるため凸集合です。
有限個の凸集合のミンコフスキー和は凸集合
先の命題は3個以上の凸集合に関しても拡張可能です。証明では集合の個数\(n\)に関する数学的帰納法を利用します。
演習問題
\right\} \\
A_{2} &=&\left\{ \left( 0,0\right) ,\left( 1,1\right) ,\left( 1,-1\right)
\right\}
\end{eqnarray*}が与えられたとき、\(A_{1}-A_{2}\)と\(A_{2}-A_{1}\)の要素をそれぞれ特定してください。
\end{equation*}が成り立つことを証明してください。
\end{equation*}が成り立つことを証明してください。
\end{equation*}が成り立つことを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】