教材一覧
CONVEX SET

凸集合のミンコフスキー和

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

集合のミンコフスキー和

ユークリッド空間の部分集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)が与えられたとき、\(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)などと呼びます。

例(集合のミンコフスキー和)
\(\mathbb{R} ^{2}\)の部分集合\begin{eqnarray*}A_{1} &=&\left\{ \left( 1,0\right) ,\left( 0,1\right) ,\left( 0,-1\right)
\right\} \\
A_{2} &=&\left\{ \left( 0,0\right) ,\left( 1,1\right) ,\left( 1,-1\right)
\right\}
\end{eqnarray*}が与えられたとき、\begin{eqnarray*}
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\} \\
&=&A_{2}+A_{1}
\end{eqnarray*}となります。
例(集合のミンコフスキー和)
\(\mathbb{R} \)の部分集合である偶数集合を、\begin{equation*}E=\left\{ \cdots ,-4,-2,0,2,4,\cdots \right\}
\end{equation*}で表記し、奇数集合を、\begin{equation*}
O=\left\{ \cdots ,-3,-1,1,3,\cdots \right\}
\end{equation*}で表記するとき、偶数と奇数の和は奇数であることを踏まえると、\begin{equation*}
E+O=O
\end{equation*}となります。
例(空集合とのミンコフスキー和)
空集合\(\phi \)もまた\(\mathbb{R} ^{n}\)の部分集合であるため、空集合と任意の集合\(A\subset \mathbb{R} ^{n}\)のミンコフスキー和をとることができますが、\begin{equation*}A+\phi =\phi +A=\phi
\end{equation*}が成り立ちます(演習問題にします)。
例(1点集合とのミンコフスキー和)
点\(a\in \mathbb{R} ^{n}\)と集合\(A\subset \mathbb{R} ^{n}\)をそれぞれ任意に選んだとき、\begin{equation*}a+A=\left\{ a\right\} +A
\end{equation*}という表記を採用します。このとき、\begin{eqnarray*}
a+A &=&\left\{ a+x\in \mathbb{R} ^{n}\ |\ x\in A\right\} \\
&=&\left\{ x+a\in \mathbb{R} ^{n}\ |\ x\in A\right\} \\
&=&A+a
\end{eqnarray*}となります。特に、点\(a\)がゼロベクトルである場合には、\begin{equation*}0+A=A+0=A
\end{equation*}となります。
例(集合のミンコフスキー差)
ユークリッド空間の部分集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)が与えられたとき、\(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 difference)や(difference)などと呼びます。定義より、\begin{equation*}A_{1}-A_{2}=A_{1}+\left( -A_{2}\right)
\end{equation*}という関係が成り立ちます。つまり、ミンコフスキー差\(A_{1}-A_{2}\)は集合\(A_{1}\)と集合\(A_{2}\)のスカラー\(-1\)倍のミンコフスキー和として理解できます。

 

ミンコワスキー和の幾何学的解釈

集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)が与えられたとき、それらのミンコフスキー和\(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}\)が得られます。このように分割して考えることにより、ミンコワスキー和を視覚的に理解しやすくなります。

例(ミンコワスキー和の幾何学的解釈)
\(\mathbb{R} ^{2}\)の部分集合\(A\)が、\begin{equation*}A=\left\{ \left( x_{1},y_{1}\right) \in \mathbb{R} ^{2}\ |\ x_{1}^{2}+y_{1}^{2}=1\right\}
\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}\)が得られますが、これは下図のグレーの領域として描かれます。

図:ミンコフスキー和
図:ミンコフスキー和

 

凸集合のミンコフスキー和

集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)がともに凸集合である場合、それらのミンコフスキー和もまた凸集合であることが保証されます。

命題(凸集合のミンコフスキー和)
ユークリッド空間の部分集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)をそれぞれ任意に選んだとき、\(A_{1}\)と\(A_{2}\)がともに凸集合ならば\(A_{1}+A_{2}\)もまた凸集合である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(凸集合のミンコフスキー差)
繰り返しになりますが、集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)のミンコフスキー差に関して、\begin{equation*}A_{1}-A_{2}=A_{1}+\left( -A_{2}\right)
\end{equation*}という関係が成り立ちます。\(A_{1}\)と\(A_{2}\)がともに凸集合であるものとします。\(-A_{2}\)は凸集合のスカラー\(-1\)倍であるため凸集合です。したがって、\(A_{1}+\left(-A_{2}\right) \)は凸集合どうしのミンコフスキー和であるため先の命題よりこれは凸集合であり、それと等しい\(A_{1}-A_{2}\)もまた凸集合であることが示されました。つまり、凸集合どうしのミンコフスキー差もまた凸集合であるということです。

 

演習問題

問題(ミンコフスキー差)
\(\mathbb{R} ^{2}\)の部分集合\begin{eqnarray*}A_{1} &=&\left\{ \left( 1,0\right) ,\left( 0,1\right) ,\left( 0,-1\right)
\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}\)の要素をそれぞれ特定してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ミンコフスキー和の交換律)
集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)を任意に選んだとき、\begin{equation*}A_{1}+A_{2}=A_{2}+A_{1}
\end{equation*}が成り立つことを証明してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(ミンコフスキー和の結合律)
集合\(A_{1},A_{2},A_{3}\subset \mathbb{R} ^{n}\)を任意に選んだとき、\begin{equation*}\left( A_{1}+A_{2}\right) +A_{3}=A_{1}+\left( A_{2}+A_{3}\right)
\end{equation*}が成り立つことを証明してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(空集合とのミンコフスキー和)
任意の集合\(A\subset \mathbb{R} ^{n}\)について、\begin{equation*}A+\phi =\phi +A=\phi
\end{equation*}が成り立つことを証明してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回は凸集合どうしの凸結合について解説します。

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録