教材一覧
教材一覧
教材検索

凸集合

半空間(閉半空間・開半空間)

目次

Twitter
Mailで保存

半空間(閉半空間)

ユークリッド空間\(\mathbb{R} ^{n}\)における超平面とは、非ゼロの法線ベクトル\(a=\left( a_{1},\cdots ,a_{n}\right) \in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)から、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x=c\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ a_{1}x_{1}+\cdots +a_{n}x_{n}=c\right\}
\end{eqnarray*}と定義される\(\mathbb{R} ^{n}\)の部分集合です。超平面\(H\left( a,c\right) \)が与えられれば、空間\(\mathbb{R} ^{n}\)を以下の2つの領域に分割することができます。1つは、\begin{eqnarray*}H^{+}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\geq c\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ a_{1}x_{1}+\cdots +a_{n}x_{n}\geq c\right\}
\end{eqnarray*}であり、これを超平面\(H\left( a,c\right) \)の上半空間(halfspace above \(H\left( a,c\right) \))と呼びます。もう1つは、\begin{eqnarray*}H^{-}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\leq c\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ a_{1}x_{1}+\cdots +a_{n}x_{n}\leq c\right\}
\end{eqnarray*}であり、これを超平面\(H\left( a,c\right) \)の下半空間(halfspace below \(H\left( a,c\right) \))と呼びます。上半空間と下半空間を総称して半空間(halfspace)や閉半空間(closed halfspace)などと呼びます。

空間と超平面および半空間の間には以下の関係が成り立ちます。

命題(半空間による空間の分割)
ユークリッド空間\(\mathbb{R} ^{n}\)における超平面\(H\left(a,c\right) \)を任意に選んだとき、以下の関係\begin{eqnarray*}&&\left( a\right) \ \mathbb{R} ^{n}=H^{+}\left( a,c\right) \cup H^{-}\left( a,c\right) \\
&&\left( b\right) \ H\left( a,c\right) \subset H^{+}\left( a,c\right) \\
&&\left( c\right) \ H\left( a,c\right) \subset H^{-}\left( a,c\right) \\
&&\left( d\right) \ H\left( a,c\right) =H^{+}\left( a,c\right) \cap
H^{-}\left( a,c\right)
\end{eqnarray*}が成り立つ。

証明

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

つまり、空間\(\mathbb{R} ^{n}\)は上半空間と下半空間に分割されますが、上半空間と下半空間は互いに素ではなく、両者の交わりは超平面と一致します。言い換えると、空間\(\mathbb{R} ^{n}\)は超平面を境に上半空間と下半空間に分割されるということです。ただし、繰り返しになりますが、上半空間と下半空間は互いに素ではありません。

例(超平面による1次元空間の分割)
1次元ユークリッド空間における超平面と半空間は、法線ベクトル\(a\in \mathbb{R} \backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)を用いて、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ x\in \mathbb{R} \ |\ ax=c\right\} =\left\{ \frac{c}{a}\right\} \\
H^{+}\left( a,c\right) &=&\left\{ x\in \mathbb{R} \ |\ ax\geq c\right\} =\left[ \frac{c}{a},+\infty \right) \\
H^{-}\left( a,c\right) &=&\left\{ x\in \mathbb{R} \ |\ ax\leq c\right\} =\left( -\infty ,\frac{c}{a}\right] \end{eqnarray*}と定義されます。\(\mathbb{R} \)における超平面は点です。数直線\(\mathbb{R} \)は超平面\(H\left( a,c\right) \)に相当する点によって、上半空間\(H^{+}\left( a,c\right) \)に相当する区間と、下半空間\(H^{-}\left( a,c\right) \)に相当する区間に分割されます。
例(超平面による2次元空間の分割)
2次元ユークリッド空間における超平面と半空間は、法線ベクトル\(a=\left( a_{1},a_{2}\right) \in \mathbb{R} ^{2}\backslash \left\{ \left( 0,0\right) \right\} \)とスカラー\(c\in \mathbb{R} \)を用いて、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{1}x_{1}+a_{2}x_{2}=c\right\} \\
H^{+}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{1}x_{1}+a_{2}x_{2}\geq c\right\} \\
H^{-}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{1}x_{1}+a_{2}x_{2}\leq c\right\}
\end{eqnarray*}と定義されます。\(\mathbb{R} ^{2}\)における超平面は直線です。平面\(\mathbb{R} ^{2}\)は超平面\(H\left( a,c\right) \)に相当する直線によって、上半空間\(H^{+}\left( a,c\right) \)に相当する領域と、下半空間\(H^{-}\left( a,c\right) \)に相当する領域に分割されます。
例(超平面による3次元空間の分割)
3次元ユークリッド空間における超平面と半空間は、法線ベクトル\(a=\left( a_{1},a_{2},a_{3}\right) \in \mathbb{R} ^{3}\backslash \left\{ \left( 0,0,0\right) \right\} \)とスカラー\(c\in \mathbb{R} \)を用いて、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ \left( x_{1},x_{2},x_{3}\right) \in \mathbb{R} ^{3}\ |\ a_{1}x_{1}+a_{2}x_{2}+a_{3}=c\right\} \\
H^{+}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2},x_{3}\right) \in \mathbb{R} ^{3}\ |\ a_{1}x_{1}+a_{2}x_{2}+a_{3}\geq c\right\} \\
H^{-}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2},x_{3}\right) \in \mathbb{R} ^{3}\ |\ a_{1}x_{1}+a_{2}x_{2}+a_{3}\leq c\right\}
\end{eqnarray*}と定義されます。\(\mathbb{R} ^{3}\)における超平面は平面です。空間\(\mathbb{R} ^{3}\)は超平面\(H\left( a,c\right) \)に相当する平面によって、上半空間\(H^{+}\left( a,c\right) \)に相当する領域と、下半空間\(H^{-}\left( a,c\right) \)に相当する領域に分割されます。

 

開半空間

ユークリッド空間\(\mathbb{R} ^{n}\)は超平面を境に上半空間と下半空間に分割されることが明らかになりました。ただし、上半空間と下半空間は互いに素ではなく、両者の交わりは超平面と一致します。したがって、上半空間から超平面を除き、下半空間から超平面を除けば、互いに交わらない\(\mathbb{R} ^{n}\)の2つの部分集合が得られます。さらに、それらに超平面を加えれば、空間\(\mathbb{R} ^{n}\)を互いに素な3つの部分集合に分割できます。具体的には以下の通りです。

繰り返しになりますが、非ゼロの法線ベクトル\(a=\left( a_{1},\cdots ,a_{n}\right) \in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)が与えられたとき、超平面と半空間はそれぞれ、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x=c\right\} \\
H^{+}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\geq c\right\} \\
H^{-}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\leq c\right\}
\end{eqnarray*}と定義されます。以上を踏まえると、上半空間\(H^{+}\left( a,c\right) \)から超平面\(H\left( a,c\right) \)の点を除いて得られる集合は、\begin{eqnarray*}H^{++}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x>c\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ a_{1}x_{1}+\cdots +a_{n}x_{n}>c\right\}
\end{eqnarray*}となりますが、これを超平面\(H\left( a,c\right) \)の上開半空間(open halfspace above \(H\left(a,c\right) \))と呼びます。一方、下半空間\(H^{-}\left( a,c\right) \)から超平面\(H\left( a,c\right) \)の点を除いて得られる集合は、\begin{eqnarray*}H^{− −}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x<c\right\} \\
&=&\left\{ \left( x_{1},\cdots ,x_{n}\right) \in \mathbb{R} ^{n}\ |\ a_{1}x_{1}+\cdots +a_{n}x_{n}<c\right\}
\end{eqnarray*}となりますが、これを超平面\(H\left( a,c\right) \)の下開半空間(open halfspace below \(H\left(a,c\right) \))と呼びます。上開半空間と下開半空間を総称して開半空間(open halfspace)と呼びます。

空間と超平面および開半空間の間には以下の関係が成り立ちます。

命題(半空間による空間の分割)
ユークリッド空間\(\mathbb{R} ^{n}\)における超平面\(H\left(a,c\right) \)を任意に選んだとき、以下の関係\begin{eqnarray*}&&\left( a\right) \ \mathbb{R} ^{n}=H\left( a,c\right) \cup H^{++}\left( a,c\right) \cup H^{− −}\left(
a,c\right) \\
&&\left( b\right) \ H\left( a,c\right) \cap H^{++}\left( a,c\right) =\phi \\
&&\left( c\right) \ H\left( a,c\right) \cap H^{− −}\left( a,c\right) =\phi \\
&&\left( d\right) \ H^{++}\left( a,c\right) \cap H^{− −}\left( a,c\right)
=\phi
\end{eqnarray*}が成り立つ。

証明

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

つまり、空間\(\mathbb{R} ^{n}\)は超平面と上開半区間と下開半区間に分割されるとともに、これら3つの集合はお互いに互いに素であると言うことです。

例(超平面による1次元空間の分割)
1次元ユークリッド空間における超平面と開半空間は、法線ベクトル\(a\in \mathbb{R} \backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)を用いて、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ x\in \mathbb{R} \ |\ ax=c\right\} =\left\{ \frac{c}{a}\right\} \\
H^{++}\left( a,c\right) &=&\left\{ x\in \mathbb{R} \ |\ ax>c\right\} =\left( \frac{c}{a},+\infty \right) \\
H^{− −}\left( a,c\right) &=&\left\{ x\in \mathbb{R} \ |\ ax<c\right\} =\left( -\infty ,\frac{c}{a}\right)
\end{eqnarray*}と定義されます。\(\mathbb{R} \)における超平面は点です。数直線\(\mathbb{R} \)は超平面\(H\left( a,c\right) \)に相当する点と上開半空間\(H^{++}\left( a,c\right) \)に相当する区間および下開半空間\(H^{− −}\left( a,c\right) \)に相当する区間に分割されます。これら3つの集合は互いに素です。
例(超平面による2次元空間の分割)
2次元ユークリッド空間における超平面と開半空間は、法線ベクトル\(a=\left( a_{1},a_{2}\right) \in \mathbb{R} ^{2}\backslash \left\{ \left( 0,0\right) \right\} \)とスカラー\(c\in \mathbb{R} \)を用いて、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{1}x_{1}+a_{2}x_{2}=c\right\} \\
H^{++}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{1}x_{1}+a_{2}x_{2}>c\right\} \\
H^{− −}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R} ^{2}\ |\ a_{1}x_{1}+a_{2}x_{2}<c\right\}
\end{eqnarray*}と定義されます。\(\mathbb{R} ^{2}\)における超平面は直線です。平面\(\mathbb{R} ^{2}\)は超平面\(H\left( a,c\right) \)に相当する直線と上開半空間\(H^{+-}\left( a,c\right) \)に相当する領域および下開半空間\(H^{− −}\left( a,c\right) \)に相当する領域に分割されます。これら3つの集合は互いに素です。
例(超平面による3次元空間の分割)
3次元ユークリッド空間における超平面と開半空間は、法線ベクトル\(a=\left( a_{1},a_{2},a_{3}\right) \in \mathbb{R} ^{3}\backslash \left\{ \left( 0,0,0\right) \right\} \)とスカラー\(c\in \mathbb{R} \)を用いて、\begin{eqnarray*}H\left( a,c\right) &=&\left\{ \left( x_{1},x_{2},x_{3}\right) \in \mathbb{R} ^{3}\ |\ a_{1}x_{1}+a_{2}x_{2}+a_{3}=c\right\} \\
H^{++}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2},x_{3}\right) \in \mathbb{R} ^{3}\ |\ a_{1}x_{1}+a_{2}x_{2}+a_{3}>c\right\} \\
H^{− −}\left( a,c\right) &=&\left\{ \left( x_{1},x_{2},x_{3}\right) \in \mathbb{R} ^{3}\ |\ a_{1}x_{1}+a_{2}x_{2}+a_{3}<c\right\}
\end{eqnarray*}と定義されます。\(\mathbb{R} ^{3}\)における超平面は平面です。空間\(\mathbb{R} ^{3}\)は超平面\(H\left( a,c\right) \)に相当する平面と上開半空間\(H^{++}\left( a,c\right) \)に相当する領域および下開半空間\(H^{− −}\left( a,c\right) \)に相当する領域に分割されます。これら3つの集合は互いに素です。

 

超平面と半区間の位置関係

ユークリッド空間\(\mathbb{R} ^{n}\)における超平面\(H\left(a,c\right) \)が与えられたとき、半空間や半閉空間の定義より、点\(x\in \mathbb{R} ^{n}\)を任意に選んだとき、\begin{eqnarray*}&&\left( a\right) \ x\in H\left( a,c\right) \Leftrightarrow a\cdot x=c \\
&&\left( b\right) \ x\in H^{+}\left( a,c\right) \Leftrightarrow a\cdot x\geq
c \\
&&\left( c\right) \ x\in H^{-}\left( a,c\right) \Leftrightarrow a\cdot x\leq
c \\
&&\left( d\right) \ x\in H^{++}\left( a,c\right) \Leftrightarrow a\cdot x>c
\\
&&\left( e\right) \ x\in H^{− −}\left( a,c\right) \Leftrightarrow a\cdot x<c
\end{eqnarray*}などの関係が成り立つため、与えられた点\(x\)が属する空間を判定するためには内積\(a\cdot x\)とスカラー\(c\)を比較することが基本的な方針になります。ただ、以下の命題を用いて判定することもできます。

命題(超平面と半区間の位置関係)
ユークリッド空間\(\mathbb{R} ^{n}\)における超平面\(H\left(a,c\right) \)および\(x_{0}\in H\left( a,c\right) \)を満たす点\(x_{0}\in \mathbb{R} ^{n}\)をそれぞれ任意に選ぶ。点\(x\in \mathbb{R} ^{n}\)を任意に選んだとき、\begin{eqnarray*}&&\left( a\right) \ x\in H\left( a,c\right) \Leftrightarrow a\cdot \left(
x-x_{0}\right) =0 \\
&&\left( b\right) \ x\in H^{+}\left( a,c\right) \Leftrightarrow a\cdot
\left( x-x_{0}\right) \geq 0 \\
&&\left( c\right) \ x\in H^{-}\left( a,c\right) \Leftrightarrow a\cdot
\left( x-x_{0}\right) \leq 0 \\
&&\left( d\right) \ x\in H^{++}\left( a,c\right) \Leftrightarrow a\cdot
\left( x-x_{0}\right) >0 \\
&&\left( e\right) \ x\in H^{− −}\left( a,c\right) \Leftrightarrow a\cdot
\left( x-x_{0}\right) <0
\end{eqnarray*}などの関係が成り立つ。

証明

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

以上の命題より、超平面の法線ベクトル\(a\)と超平面上の点\(x_{0}\)が与えられたとき、それぞれの点\(x\in \mathbb{R} ^{n}\)について、\begin{eqnarray*}&&\left( a\right) \ x\in H\left( a,c\right) \Leftrightarrow a\text{と}x-x_{0}\text{のなす角が直角} \\
&&\left( b\right) \ x\in H^{+}\left( a,c\right) \Leftrightarrow a\text{と}x-x_{0}\text{のなす角が直角または鋭角} \\
&&\left( c\right) \ x\in H^{-}\left( a,c\right) \Leftrightarrow a\text{と}x-x_{0}\text{のなす角が直角または鈍角} \\
&&\left( d\right) \ x\in H^{++}\left( a,c\right) \Leftrightarrow a\text{と}x-x_{0}\text{のなす角が直角} \\
&&\left( e\right) \ x\in H^{− −}\left( a,c\right) \Leftrightarrow a\text{と}x-x_{0}\text{のなす角が鈍角}
\end{eqnarray*}という関係が成り立つことが明らかになりました。つまり、与えられた点\(x\)が属する空間を判定するためには、超平面上の点\(x_{0}\)を任意に選んだ上で、それを始点とするベクトル\(x-x_{0}\)と超平面の法線ベクトル\(a\)のなす角の大きさを見ればよいということです。

 

演習問題

問題(半空間・開半区間は凸集合)
法線ベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)をそれぞれ任意に選んだとき、半空間および開半空間\begin{eqnarray*}H^{+}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\geq c\right\} \\
H^{-}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\leq c\right\} \\
H^{++}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x>c\right\} \\
H^{− −}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x<c\right\}
\end{eqnarray*}はいずれも\(\mathbb{R} ^{n}\)上の凸集合であることを示してください。
証明

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

Twitter
Mailで保存

質問とコメント