分離超平面定理のソースを表示

[[File:Separating axis theorem2008.png|right|thumb|分離超平面定理の概略図。]]
'''分離超平面定理'''（ぶんりちょうへいめんていり、{{lang-en-short|separating hyperplane theorem, hyperplane separation theorem}}）は {{mvar|n}} 次元[[ユークリッド空間]]上の[[素集合|互いに素]]な[[凸集合]]に関する[[幾何学]]における 2 つの[[定理]]を指す。
<!--
In [[geometry]], the '''hyperplane separation theorem''' is either of two theorems about disjoint [[convex set]]s in ''n''-dimensional [[Euclidean space]].
-->

一つ目の定理は、互いに素な凸集合の両方が[[閉集合]]であってかつ少なくともいずれか 1 つの凸集合が[[コンパクト集合]]である場合、2 つの閉凸集合の間に 1 つの超平面が存在でき、また閉凸集合の間に 2 つの平行な超平面を隙間を作って置くことができることを示す。
<!--
In the first version of the theorem, if both these sets are closed and at least one of them is compact, then there is a hyperplane in between them and even two parallel hyperplanes in between them separated by a gap.  
-->

二つ目の定理は、互いに素な凸集合があり両者が[[開集合]]である場合、2 つの開凸集合の間に 1 つの超平面をはさむことができるが、2 つの開凸集合の間には必ずしも隙間が存在するわけではないことを示す（従って第一の定理と異なり、複数の超平面を重ねずに挟むことができない状況が存在する）。
<!--
In the second version, if both disjoint convex sets are open, then there is a hyperplane in between them, but not necessarily any gap.
--> 

分離超平面に対して[[直交]]する[[座標軸|軸]]を'''分離軸''' {{en|(separating axis)}} と呼ぶ。これは、2 つの{{仮リンク|凸体|en|convex body}}の分離軸への直交写像が互いに素であることによる。
<!--
An axis which is orthogonal to a separating hyperplane is a '''separating axis''', because the orthogonal projections of the convex bodies onto the axis are disjoint.
-->

分離超平面定理は[[ヘルマン・ミンコフスキー]]の寄与によって発見された。[[ハーン＝バナッハの分離定理]]はミンコフスキーの結果を[[線型位相空間]]へ一般化したものである。
<!--
The hyperplane separation theorem is due to [[Hermann Minkowski]]. The [[Hahn–Banach_theorem#Hahn–Banach_separation_theorem|Hahn–Banach separation theorem]] generalizes the result to [[topological vector spaces]].
-->

関連する結果として{{仮リンク|支持超平面定理|en|supporting hyperplane theorem}}がある。'''マージン最大化超平面''' {{en|(maximum-margin hyperplane)}} は空間上にある点の集まりを 2 つのクラスタに分離する超平面の中で、両者のクラスタからの[[距離空間|距離]]が等しいようなものである。このとき、それぞれのクラスタと分離超平面の間の[[マージン]]は最大化される。この事実は[[サポートベクターマシン]]などに応用される。
<!--
A related result is the [[supporting hyperplane theorem]]. In [[geometry]], a '''maximum-margin hyperplane''' is a [[hyperplane]] which separates two 'clouds' of points and is at equal distance from the two. The margin between the hyperplane and the clouds is maximal. See the article on [[Support Vector Machines]] for more details.
-->

== ステートメントと証明 ==
{{math_theorem|name=分離超平面定理{{sfn|Boyd|Vandenberghe|2004|loc=Exercise 2.22.}}|{{mvar|A}} と {{mvar|B}} をそれぞれ {{math|'''R'''<sup>''n''</sup>}} の[[素集合|互いに素]]な[[空集合|空]]でない[[凸集合|凸部分集合]]であるとする。そのような集合について、すべての {{mvar|A}} の[[元 (数学)|元]] {{math|''x'' &isin; ''A''}} と {{mvar|B}} の元 {{math|''y'' &isin; ''B''}} の組に対して
:<math>\langle x, v \rangle \ge c \, \text{ and } \langle y, v \rangle \le c</math>
を満たす零でない[[ベクトル空間|ベクトル]] {{mvar|v}} と[[実数]] {{mvar|c}} が存在する。つまり、{{mvar|v}} を[[法線ベクトル]]とする[[超平面]] {{math|1=&#x3008;&middot;, ''v''&#x3009; = ''c''}} によって {{mvar|A}} と {{mvar|B}} を分離できる。}}
<!--
{{math_theorem|name=Hyperplane separation theorem<ref>{{harvnb|Boyd–Vandenberghe|loc=Exercise 2.22.}}</ref>|Let ''A'' and ''B'' be two disjoint nonempty convex subsets of '''R'''<sup>''n''</sup>. Then there exists a nonzero vector ''v'' and a real number ''c'' such that
:<math>\langle x, v \rangle \ge c \, \text{ and } \langle y, v \rangle \le c</math>
for all ''x'' in ''A'' and ''y'' in ''B''; i.e., the hyperplane <math>\langle \cdot, v \rangle = c</math>, ''v'' the normal vector, separates ''A'' and ''B''.
}}
-->

証明は以下の[[補題]]に基づく：
{{math_theorem|name=補題{{anchors|補題のステートメント}}|{{mvar|K}} を {{math|'''R'''<sup>''n''</sup>}} の空でない閉凸部分集合とする。集合 {{mvar|K}} について、{{mvar|K}} 上の最小[[ノルム]]を持つベクトルが一意に存在する。}}
<!--
The proof is based on the following lemma:

{{math_theorem|name=Lemma|Let ''K'' be a nonempty closed convex subset of '''R'''<sup>''n''</sup>. Then there exists a unique vector in ''K'' of minimum norm (length).}}
-->

;補題の証明{{anchors|補題の証明}}：
{{mvar|K}} 上のベクトル {{mvar|x}} のノルムの下限を {{math|1=''&delta;'' = inf{{(}}{{mabs|''x''}}&thinsp;{{!}}&thinsp;''x'' &isin; ''K''{{)}}}} とする。{{math|{{mabs|''x<sub>j</sub>''}} &rarr; ''&delta;''}} となるような {{mvar|K}} 上の数列 {{mvar|x<sub>j</sub>}} について、{{mvar|K}} の凸性より {{math|{{mabs|''x<sub>i</sub>'' + ''x<sub>j</sub>''}}/2 &isin; ''K''}} が成り立つ。また、
:<math>\left|\frac{x_i + x_j}{2}\right| \ge \inf\{|x|\} = \delta</math>
であることから
:<math> |x_i - x_j|^2 = 2|x_i|^2 + 2|x_j|^2 - |x_i + x_j|^2 \le 2|x_i|^2 + 2|x_j|^2 - 4\delta^2</math>
が得られる。上記の関係について極限を取れば右辺は 0 となり、従って
:<math>|x_i - x_j| \le 0</math>
を満たす。すなわち {{mvar|x<sub>i</sub>}} は[[コーシー列]]であり、Kは完備であるからその極限値は {{mvar|K}} に含まれるので、{{mvar|&delta;}} はベクトル {{math|''x'' &isin; ''K''}} の最小ノルムとなる。最小ノルムを持つベクトルの一意性について、ベクトル {{math|''y'' &isin; ''K''}} が最小ノルム {{mvar|&delta;}} を持つならば、
:<math>|x - y|^2 \le 2|x|^2 + 2|y|^2 - 4\delta^2 = 0</math>
となるから {{math|1=''x'' = ''y''}} である。□
<!--
'''Proof of lemma''': Let <math>\delta = \inf \{ |x| \mid x \in K \}.</math> Let <math>x_j</math> be a sequence in ''K'' such that <math>|x_j| \to \delta</math>. Note that <math>(x_i + x_j)/2</math> is in ''K'' since ''K'' is convex and so <math>|x_i + x_j|^2 \ge 4 \delta^2</math>.
Since
:<math>|x_i - x_j|^2 = 2|x_i|^2 + 2|x_j|^2 - |x_i + x_j|^2 \le 2|x_i|^2 + 2|x_j|^2 - 4\delta^2 \to 0</math>
as <math>i, j \to \infty</math>, <math>x_i</math> is a [[Cauchy sequence]] and so has limit ''x'' in ''K''. It is unique since if ''y'' is in ''K'' and has norm δ, then<math>|x - y|^2 \le 2|x|^2 + 2|y|^2 - 4\delta^2 = 0</math>and ''x'' = ''y''. <math>\square</math>
-->

;定理の証明：
互いに素な空でない凸集合 {{math|''A'', ''B''}} が与えられるとして、次のような{{仮リンク|ミンコフスキー和|en|Minkowski sum}}を考える。
:<math>K = A + (-B) = \{ x - y \mid x \in A, y \in B \}.</math>
{{mvar|B}} は凸なので {{math|&minus;''B''}} もまた凸である。{{mvar|A}} と {{math|&minus;''B''}}の（したがって {{mvar|B}} の）凸性から上記のミンコフスキー和 {{mvar|K}} は凸である。
<!--
'''Proof of theorem''':
Given disjoint nonempty convex sets ''A'', ''B'', let
:<math>K = A + (-B) = \{ x - y \mid x \in A, y \in B \}.</math>
Since <math>-B</math> is convex and the [[Minkowski sum|sum]] of convex sets is convex, ''K'' is convex.
-->

{{mvar|K}} の[[閉包 (位相空間論)|閉包]] {{math|{{overline|''K''}}}} は凸なので、[[#補題|先に示した補題]]より {{math|{{overline|''K''}}}} について最小ノルムを持つベクトル {{mvar|v}} が一意に定まる。{{math|{{overline|''K''}}}} の凸性から、任意のベクトル {{math|''u'' &isin; ''K''}} について、線分
:<math>v + t(u - v), \, 0 \le t \le 1</math>
上の点はすべて {{math|{{overline|''K''}}}} に含まれるため、閉包 {{math|{{overline|''K''}}}} のベクトルのノルムについて以下の関係が成り立つ。
:<math>|v|^2 \le |v + t(u - v)|^2 = |v|^2 + 2 t \langle v, u - v \rangle + t^2|u - v|^2, \quad (0 \le t \le 1).</math>
この関係より直ちに次の結果が得られる：
:<math>0 \le 2 \langle v, u \rangle - 2 |v|^2 + t|u - v|^2, \quad (0 < t \le 1).</math>
更に、{{mvar|t}} について {{math|''t'' &rarr; 0}} の極限を取れば上記の関係は
:<math>\langle v, u \rangle \ge |v|^2 </math>
と書き換えられる。従って、任意の {{math|''x'' &isin; ''A''}} および {{math|''y'' &isin; ''B''}} について、
:<math>\langle v, x - y \rangle \ge |v|^2 </math>
が成り立つ。
<!--
By the lemma, the closure <math>\overline{K}</math> of ''K'', which is convex, contains a vector ''v'' of minimum norm. Since <math>\overline{K}</math> is convex, for any ''x'' in ''K'', the line segment
:<math>v + t(x - v), \, 0 \le t \le 1</math>
lies in <math>\overline{K}</math> and so
:<math>|v|^2 \le |v + t(x - v)|^2 = |v|^2 + 2 t \langle v, x - v \rangle + t^2|x-v|^2</math>.
For <math>0 < t \le 1</math>, we thus have:
:<math>0 \le 2 \langle v, x \rangle - 2 |v|^2 + t|x-v|^2</math>
and letting <math>t \to 0</math> gives: <math>\langle x, v \rangle \ge |v|^2</math>. Hence, for any ''x'' in ''A'' and ''y'' in ''B'', we have: <math>\langle x - y, v \rangle \ge |v|^2</math>.
-->

ベクトル {{mvar|v}} が零ベクトルでないならば、この関係より
:<math>\inf_{x \in A} \langle x, v \rangle \ge |v|^2 + \sup_{y \in B} \langle y, v \rangle</math>
を得て証明を終わる。
<!--
Thus, if ''v'' is nonzero, the proof is complete since
:<math>\inf_{x \in A} \langle x, v \rangle \ge |v|^2 + \sup_{y \in B} \langle y, v \rangle.</math>
In general, if the interior of ''K'' is nonempty, then it can be exhausted by compact convex subsets <math>K_n</math>. Since 0 is not in ''K'', each <math>K_n</math> contains a nonzero vector <math>v_n</math> of minimum length and by the argument in the early part, we have: <math>\langle x, v_n \rangle \ge 0</math> for any <math>x \in K_n</math>. We also normalize them to have length one; then the sequence <math>v_n</math> contains a convergent subsequence with limit ''v'', which has length one and is nonzero. We have <math>\langle x, v \rangle \ge 0</math> for any ''x'' in the interior of ''K'' and by continuity the same holds for all ''x'' in ''K''. We now finish the proof as before. Finally, if ''K'' has empty interior, the [[affine set]] that it spans has dimension less than that of the whole space. Consequently ''K'' is contained in some hyperplane <math>\langle \cdot, v \rangle = c</math>; thus, <math>\langle x, v \rangle \ge c</math> for all ''x'' in ''K'' and we finish the proof as before. <math>\square</math>

The above proof also proves the first version of the theorem mentioned in the lede (to see it, note that ''K'' is closed under the hypothesis below.)

{{math_theorem|name=Separation theorem I| Let ''A'' and ''B'' be two disjoint nonempty closed convex sets, one of which is compact. Then there exists a nonzero vector ''v'' and real numbers <math>c_1 < c_2</math> such that
:<math>\langle x, v \rangle > c_2 \, \text{ and } \langle y, v \rangle < c_1</math>
for all ''x'' in ''A'' and ''y'' in ''B''.
}}

Here, the compactness in the hypothesis cannot be relaxed; see an example in the next section. Also,

{{math_theorem|name=Separation theorem II| Let ''A'' and ''B'' be two disjoint nonempty convex sets. If ''A'' is open, then there exists a nonzero vector ''v'' and real number <math>c</math> such that
:<math>\langle x, v \rangle > c \, \text{ and } \langle y, v \rangle \le c</math>
for all ''x'' in ''A'' and ''y'' in ''B''.
}}

This follows from the standard version since the separating hyperplane cannot intersect the interiors of the convex sets.
-->== 反例と一意性 == 
[[File:Separating axis theorem2.svg|right|thumb|'''定理の適用できないケース'''：一方（または両方）の集合が凸でない]]
{{mvar|A}} または {{mvar|B}} の一方が[[凸集合]]でない場合、「分離定理」に対しては様々な反例が挙げられる。例えば {{mvar|A}} と {{mvar|B}} は[[同心円]]状にとることができる。
<!--
If one of ''A'' or ''B'' is not convex, then there are many possible counterexamples.  For example, ''A'' and ''B'' could be concentric circles.
-->

より微妙な反例として、{{mvar|A}} と {{mvar|B}} の両方が閉凸集合だがいずれも[[コンパクト集合|コンパクト]]でない場合が挙げられる。例として、{{mvar|A}} が閉半平面で {{mvar|B}} が[[双曲線]]の分枝の一方であるとすれば、この場合には分離超平面は厳密には存在しない（しかしながら、開凸集合に関する分離定理があるために {{mvar|A}} および {{mvar|B}} の[[内部 (位相空間論)|内部]]を分離する超平面が 1 つ存在する）：
:<math>A = \{(x,y) : x \le 0\}</math>
:<math>B = \{(x,y) : x > 0, y \geq 1/x \}.\ </math>
<!--
A more subtle counterexample is one in which ''A'' and ''B'' are both closed but neither one is compact.  For example, if ''A'' is a closed half plane and B is bounded by one arm of a hyperbola, then there is no strictly separating hyperplane:

:<math>A = \{(x,y) : x \le 0\}</math>
:<math>B = \{(x,y) : x > 0, y \geq 1/x \}.\ </math>

(Although, by an instance of the second theorem, there is a hyperplane that separates their interiors.)  
-->

他のタイプの反例として {{mvar|A}} がコンパクトな閉凸集合であり {{mvar|B}} が開凸集合である場合がある。例えば、{{mvar|A}} を正方形の閉集合、{{mvar|B}} を正方形の開集合として {{mvar|A}} と {{mvar|B}} が接している状況がこれに当てはまる。
<!--
Another type of counterexample has ''A'' compact and ''B'' open.  For example, A can be a closed square and B can be an open square that touches ''A''.
-->

閉凸集合に関する分離定理では分離超平面を一意に決めることができないことは明らかである。開集合バージョンの分離定理では、超平面が一意に定まる場合もあるしそうでない場合もあり得る。技術的なことだがこれらのことは分離軸について言い換えられる。閉凸集合の分離定理では分離軸を一意に決められないが、開凸集合の分離定理では分離軸を一意に決定できる。
<!--
In the first version of the theorem, evidently the separating hyperplane is never unique.  In the second version, it may or may not be unique.  Technically a separating axis is never unique because it can be translated; in the second version of the theorem, a separating axis can be unique up to translation.
-->

== 衝突判定への応用 ==
<!--
'''The separating axis theorem''' (SAT) says that:

Two convex objects do not overlap if there exists a line (called axis) onto which the two objects' projections do not overlap.

SAT suggests an algorithm for testing whether two convex solids intersect or not. 

Regardless of dimensionality, the separating axis is always a line.
For example, in 3D, the space is separated by planes, but the separating axis is perpendicular to the separating plane.

The separating axis theorem can be applied for fast [[collision detection]] between polygon meshes. Each [[face (geometry)|face]]'s [[surface normal|normal]] or other feature directions is used as a separating axis, as well as the cross products. Note that this yields possible separating axes, not separating lines/planes.

If the cross products were not used, certain edge-on-edge non-colliding cases would be treated as colliding. For increased efficiency, parallel axes may be calculated as a single axis.
-->
== 関連項目 ==
*[[双対錐と極錐|双対錐]]
* {{仮リンク|ファルカスの補題|en|Farkas' lemma}}

== 脚注 ==
{{reflist}}

== 参考文献 ==
*{{cite book
 | first1     = Stephen P. 
 | last1      = Boyd 
 | first2     = Lieven
 | last2      = Vandenberghe
 | title      = Convex Optimization 
 | date       = 2004
 | publisher  = Cambridge University Press
 | isbn       = 978-0-521-83378-3 
 | url        = http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf 
 | format     = pdf
 | ref        = harv
}}
*{{cite book
 | last1      = Golshtein
 | first1     = E. G.
 | last2      = Tretyakov
 | first2     = N.V.
 | title      = Modified Lagrangians and monotone maps in optimization
 | publisher  = New York: Wiley
 | date       = 1996
 | isbn       = 0-471-54821-9
 | page       = 6
 | ref        = harv
}}
*{{cite book
 | last1      = Shimizu
 | first1     = Kiyotaka 
 | last2      = Ishizuka 
 | first2     = Yo 
 | last3      = Bard
 | first3     = Jonathan F.
 | title      = Nondifferentiable and two-level mathematical programming
 | publisher  = Boston: Kluwer Academic Publishers
 | date       = 1997
 | isbn       = 0-7923-9821-1
 | page       = 19
 | ref        = harv
}}

== 外部リンク ==
* [http://www.metanetsoftware.com/technique/tutorialA.html Collision detection and response]

{{DEFAULTSORT:ふんりちようへいめんていり}}
[[Category:幾何学の定理]]
[[Category:ヘルマン・ミンコフスキー]]
[[Category:数学に関する記事]]