点の存在範囲と凸結合

同義語：convex combinations and regions of points

概要

点の存在範囲と凸結合（convex combinations and regions of points）とは、三角形 $OAB$ で $\vec a=\overrightarrow{OA}$、$\vec b=\overrightarrow{OB}$ とし、$\overrightarrow{OP}=s\vec a+t\vec b$ の係数 $s,t$ に条件を付けたときに点 $P$ の動く範囲を、斜交座標の図形として読むことである。$s\ge0$、$t\ge0$、$s+t\le1$ の範囲は三角形 $OAB$ の周と内部である。$s,t$ の 1 次不等式は半平面を表すので、1 次の条件の範囲は、$st$ 平面の同じ図形（多角形・半平面など）をゆがめたものになる。係数が 0 以上で和が 1 の結合を凸結合といい、三角形の周と内部は 3 頂点の凸結合の全体、つまり凸包である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ベクトル, 位置ベクトルと内分点

高校での出発点：係数に条件を付けて点を動かす

三角形 $OAB$ で $\overrightarrow{OA}=\vec a$、$\overrightarrow{OB}=\vec b$ とする。$\vec a$、$\vec b$ は平行でないので、平面のどの点 $P$ も
$$ \overrightarrow{OP}=s\vec a+t\vec b $$
とただ 1 通りに表せる（位置ベクトルと内分点 の「平面のベクトルの分解」）。$s$、$t$ に条件を付けると、点 $P$ の動ける範囲が決まる。これを点 $P$ の 存在範囲 という。位置ベクトルと内分点 では、$s+t=1$ なら直線 $AB$、さらに $s\ge0$、$t\ge0$ なら線分 $AB$ になることを見た。この記事では、条件が不等式のときを扱う。
以下の例では、$\vec a=(4,0)$、$\vec b=(1,2)$ を使う。

いくつかの点を計算する

$\overrightarrow{OP}=s\vec a+t\vec b=(4s+t,\ 2t)$ である。

  1. $s=t=\frac14$：$P\left(\frac54,\ \frac12\right)$。$s+t=\frac12$ である。
  2. $s=t=\frac12$：$P\left(\frac52,\ 1\right)$。$s+t=1$ なので直線 $AB$ 上の点で、$s,t\ge0$ なので線分 $AB$ 上にある。実際、線分 $AB$ の中点 $\left(\frac{4+1}2,\ \frac{0+2}2\right)=\left(\frac52,1\right)$ である。
  3. $s=t=1$：$P(5,2)$。これは平行四辺形 $OACB$ の頂点 $C$（$\overrightarrow{OC}=\vec a+\vec b$）で、三角形 $OAB$ の外にある。$s+t=2>1$ である。
係数の和を一定にして点を動かす

$s\ge0$、$t\ge0$、$s+t=\frac12$ を満たす点 $P$ の範囲を求める。

  1. $s=\frac12s'$、$t=\frac12t'$ とおくと、$s'+t'=1$、$s'\ge0$、$t'\ge0$ である。
  2. $\overrightarrow{OP}=\frac12s'\vec a+\frac12t'\vec b=s'\left(\frac12\vec a\right)+t'\left(\frac12\vec b\right)$ である。
  3. $\overrightarrow{OA'}=\frac12\vec a$、$\overrightarrow{OB'}=\frac12\vec b$ となる点 $A'(2,0)$、$B'\left(\frac12,1\right)$ をとると、位置ベクトルと内分点 の「直線上にある条件」により、$P$ の範囲は線分 $A'B'$ である。$A'$、$B'$ は辺 $OA$、$OB$ の中点で、線分 $A'B'$ は辺 $AB$ に平行である（図1の破線）。

ex-ccr-start-sweep の $\frac12$ を $0$ から $1$ までの $k$ に替えると、$s+t=k$ の点は、$AB$ に平行な線分を描く。$k$ を $0$ から $1$ まで動かすと、この線分が三角形 $OAB$ を塗りつぶす。これが高校で習う「$s+t\le1$、$s\ge0$、$t\ge0$ なら三角形 $OAB$ の周と内部」の理由である。この記事では次の問いに答える。

  1. $s\ge0$、$t\ge0$、$s+t\le1$ の範囲が三角形になるのはなぜか。→ thm-ccr-triangle
  2. 条件を $s+2t\le2$ などに変えると、範囲はどうなるか。→ prop-ccr-halfplane、ex-ccr-regions
  3. 基準の点を頂点にとらないとき、三角形の周と内部はどう書けるか。→ cor-ccr-triangle-convex
  4. 大学数学では、この範囲を何とよぶか。→ def-ccr-hull、rem-ccr-simplex-cone
    高校の計算この記事での見方ボックス
    $\overrightarrow{OP}=s\vec a+t\vec b$ の $(s,t)$斜交座標def-ccr-oblique
    $s+t=k$ として $k$ で割る線分を平行に動かして三角形を塗るprf-ccr-triangle-hs
    $s\ge0$、$t\ge0$、$s+t\le1$3 つの半平面の共通部分prf-ccr-triangle-univ
    係数が $0$ 以上で和が $1$凸結合def-ccr-convex
    三角形・四面体の周と内部凸包・単体def-ccr-hull、rem-ccr-simplex-cone
    $s\ge0$、$t\ge0$ だけ錐rem-ccr-simplex-cone

斜交座標

点の斜交座標

平面に点 $O$ と、平行でない $\vec 0$ でない 2 つのベクトル $\vec a$、$\vec b$ をとる。平面の点 $P$ に対し、$\overrightarrow{OP}=s\vec a+t\vec b$ となる実数の組 $(s,t)$ はただ 1 つに決まる。この $(s,t)$ を、$O$ と $\vec a$、$\vec b$ に関する点 $P$ の 斜交座標 という。$s$ が一定の点は $\vec b$ に平行な直線上に、$t$ が一定の点は $\vec a$ に平行な直線上に並ぶ（図1の格子）。

!FORMULA[104][62490475][0]、!FORMULA[105][1802532169][0] の斜交座標の格子（!FORMULA[106][38197][0] または !FORMULA[107][38228][0] が一定の直線）と、!FORMULA[108][970877503][0]、!FORMULA[109][999506654][0]、!FORMULA[110][833088496][0] の範囲（三角形 !FORMULA[111][35664792][0]）。破線は !FORMULA[112][938395934][0] の線分。ふつうの座標の方眼を斜めにゆがめた格子で点の位置を読むことを見る図。 $\vec a=(4,0)$、$\vec b=(1,2)$ の斜交座標の格子（$s$ または $t$ が一定の直線）と、$s\ge0$、$t\ge0$、$s+t\le1$ の範囲（三角形 $OAB$）。破線は $s+t=\frac12$ の線分。ふつうの座標の方眼を斜めにゆがめた格子で点の位置を読むことを見る図。
斜交座標とふつうの座標 $(x,y)$ の関係は、連立方程式を解けば分かる。

斜交座標を座標から求める

$\vec a=(a_1,a_2)$、$\vec b=(b_1,b_2)$ は $\vec 0$ でなく平行でないとし、$D=a_1b_2-a_2b_1$ とおく。このとき $D\ne0$ であり、点 $P(x,y)$ の（原点 $O$ と $\vec a$、$\vec b$ に関する）斜交座標は
$$ s=\frac{b_2x-b_1y}{D},\qquad t=\frac{a_1y-a_2x}{D} $$
である。

$D$ が 0 でないことを示し、代入して確かめる

方針：$D=0$ なら $\vec a$、$\vec b$ が平行になることを示す。次に、式の $s$、$t$ を $s\vec a+t\vec b$ に代入して $(x,y)$ になることを確かめる。
段 1（$D\ne0$）。$D=0$ と仮定する。$\vec a\ne\vec 0$ なので、$a_1\ne0$ または $a_2\ne0$ である。$a_1\ne0$ なら、$a_1b_2=a_2b_1$ から $b_2=\frac{b_1}{a_1}a_2$ であり、$b_1=\frac{b_1}{a_1}a_1$ と合わせて $\vec b=\frac{b_1}{a_1}\vec a$ となる。$a_1=0$ なら $a_2\ne0$ で、$D=-a_2b_1=0$ から $b_1=0$、よって $\vec b=(0,b_2)=\frac{b_2}{a_2}\vec a$ となる。どちらの場合も $\vec b$ は $\vec a$ の実数倍であり、$\vec b\ne\vec 0$ なので $\vec a$ と平行である。これは仮定に反する。よって $D\ne0$ である。
段 2（代入）。式の $s$、$t$ について、$s\vec a+t\vec b$ の $x$ 成分は
$$ sa_1+tb_1=\frac{a_1(b_2x-b_1y)+b_1(a_1y-a_2x)}{D}=\frac{(a_1b_2-a_2b_1)x}{D}=x $$
である（$-a_1b_1y$ と $a_1b_1y$ が打ち消し合う）。$y$ 成分は
$$ sa_2+tb_2=\frac{a_2(b_2x-b_1y)+b_2(a_1y-a_2x)}{D}=\frac{(a_1b_2-a_2b_1)y}{D}=y $$
である（$a_2b_2x$ と $-a_2b_2x$ が打ち消し合う）。よって $s\vec a+t\vec b=(x,y)=\overrightarrow{OP}$ である。斜交座標はただ 1 つなので、これが $P$ の斜交座標である。$\square$

斜交座標を求めて三角形の内外を判定する

$\vec a=(4,0)$、$\vec b=(1,2)$ では $D=4\cdot2-0\cdot1=8$ で、lem-ccr-solve により $s=\frac{2x-y}{8}$、$t=\frac{4y}{8}=\frac y2$ である。

  1. $P(3,1)$：$s=\frac58$、$t=\frac12$。確かに $\frac58(4,0)+\frac12(1,2)=\left(\frac52+\frac12,\ 1\right)=(3,1)$。$s+t=\frac98>1$ なので、thm-ccr-triangle により三角形 $OAB$ の外にある。
  2. $P\left(2,\frac12\right)$：$s=\frac{4-\frac12}{8}=\frac7{16}$、$t=\frac14$。$s>0$、$t>0$、$s+t=\frac{11}{16}<1$ なので、三角形 $OAB$ の周の上になく、内部にある（thm-ccr-triangle の後の rem-ccr-interior）。

斜交座標で書いた 1 次の等式・不等式は、ふつうの座標でも 1 次の等式・不等式になる。

斜交座標の 1 次不等式は半平面を表す

lem-ccr-solve の状況で、実数 $\alpha$、$\beta$、$\gamma$ を $(\alpha,\beta)\ne(0,0)$ となるようにとる。斜交座標 $(s,t)$ について、$\alpha s+\beta t=\gamma$ を満たす点の全体は 1 本の直線であり、$\alpha s+\beta t\ge\gamma$ を満たす点の全体は、その直線とその片側からなる半平面である。

ふつうの座標の 1 次式に直す

方針：lem-ccr-solve の式を代入して、$x$、$y$ の 1 次式に直す。その係数が両方 $0$ にはならないことを確かめる。
段 1（代入）。lem-ccr-solve により
$$ \alpha s+\beta t=\frac{\alpha(b_2x-b_1y)+\beta(a_1y-a_2x)}{D}=\frac{c_1x+c_2y}{D},\qquad c_1=\alpha b_2-\beta a_2,\quad c_2=\beta a_1-\alpha b_1 $$
である。
段 2（係数が両方 $0$ ではない）。$c_1=c_2=0$ と仮定する。すなわち $\alpha b_2=\beta a_2$、$\alpha b_1=\beta a_1$ である。すると
$$ \alpha D=a_1(\alpha b_2)-a_2(\alpha b_1)=a_1\beta a_2-a_2\beta a_1=0 $$
で、$D\ne0$ なので $\alpha=0$ である。同じように $\beta D=(\beta a_1)b_2-(\beta a_2)b_1=\alpha b_1b_2-\alpha b_2b_1=0$ なので $\beta=0$ である。これは $(\alpha,\beta)\ne(0,0)$ に反する。よって $(c_1,c_2)\ne(0,0)$ である。
段 3（まとめ）。$\alpha s+\beta t=\gamma$ は $c_1x+c_2y=\gamma D$ と同じで、段 2 によりこれは直線の方程式である。$\alpha s+\beta t\ge\gamma$ は、$D>0$ なら $c_1x+c_2y\ge\gamma D$、$D<0$ なら両辺に $D$ を掛けて向きが変わり $c_1x+c_2y\le\gamma D$ と同じである。どちらも 1 次不等式であり、1 次不等式の表す範囲は直線とその片側である（不等式の表す領域と線形計画法 の「1 次不等式は直線の片側を表す」）。$\square$

斜交座標の不等式をふつうの座標に直す

$\vec a=(4,0)$、$\vec b=(1,2)$ で、$s=\frac{2x-y}8$、$t=\frac y2$ である（ex-ccr-oblique）。

  1. $t\ge0$ は $y\ge0$ である。境界 $t=0$ は直線 $OA$（$x$ 軸）である。
  2. $s\ge0$ は $2x-y\ge0$、すなわち $y\le2x$ である。境界 $s=0$ は直線 $OB$（$y=2x$）である。
  3. $s+t\le1$ は $\frac{2x-y}8+\frac{4y}8\le1$、すなわち $2x+3y\le8$ である。境界 $2x+3y=8$ は $A(4,0)$（$8+0=8$）と $B(1,2)$（$2+6=8$）を通るので、直線 $AB$ である。
    3 つの不等式 $y\ge0$、$y\le2x$、$2x+3y\le8$ の共通部分は、不等式の表す領域と線形計画法 で描き方を学ぶ「連立不等式の表す領域」で、三角形 $OAB$ の周と内部である。

主定理：三角形の周と内部

三角形 $OAB$ の「周と内部」は、次の 2 通りに言い表せる。

  • 辺 $AB$ 上の点 $Q$ と $O$ を結ぶ線分を、$Q$ を $A$ から $B$ まで動かしてすべて集めたもの。
  • 3 本の辺を含む直線のそれぞれについて、残りの頂点と同じ側（直線上を含む）にある点を集め、その 3 つの共通部分をとったもの。
    主定理は、どちらの言い方でも、$s\ge0$、$t\ge0$、$s+t\le1$ の範囲と一致することを述べる。
$s\ge 0$、$t\ge 0$、$s+t\le 1$ の範囲

三角形 $OAB$ で $\overrightarrow{OA}=\vec a$、$\overrightarrow{OB}=\vec b$ とする。$\overrightarrow{OP}=s\vec a+t\vec b$ で、$s$、$t$ が
$$ s\ge0,\qquad t\ge0,\qquad s+t\le1 $$
を満たしながら動くとき、点 $P$ の存在範囲を $T$ とする。次の 3 つの集合は一致する。

  1. $T$。
  2. 辺 $AB$ 上の点 $Q$ と $O$ を結ぶ線分 $OQ$ 上の点の全体。
  3. 直線 $OA$ に関して $B$ と同じ側、直線 $OB$ に関して $A$ と同じ側、直線 $AB$ に関して $O$ と同じ側（どれも直線上を含む）の 3 つの共通部分。
    すなわち $T$ は三角形 $OAB$ の周と内部である。
高校数学で解く：係数の和 $k$ で割る

方針：1 と 2 が一致することを示す。$s+t=k$ とおき、$k$ で割って係数の和を $1$ にそろえると、線分 $AB$ 上の点が現れる。
段 1（$T$ の点は線分 $OQ$ 上）。$P$ が $T$ の点で、$k=s+t$ とする。$0\le k\le1$ である。$k=0$ なら $s=t=0$ で $P=O$ であり、$O$ はどの線分 $OQ$ の上にもある。$k>0$ なら
$$ \overrightarrow{OP}=k\left(\frac sk\vec a+\frac tk\vec b\right) $$
と書ける。$\frac sk+\frac tk=1$、$\frac sk\ge0$、$\frac tk\ge0$ なので、$\overrightarrow{OQ}=\frac sk\vec a+\frac tk\vec b$ で定まる点 $Q$ は、位置ベクトルと内分点 の「直線上にある条件」により線分 $AB$ 上にある。$\overrightarrow{OP}=k\,\overrightarrow{OQ}$、$0< k\le1$ なので、$P$ は線分 $OQ$ 上にある。
段 2（線分 $OQ$ 上の点は $T$ の点）。$Q$ が線分 $AB$ 上にあれば、同じ条件により $\overrightarrow{OQ}=(1-\mu)\vec a+\mu\vec b$、$0\le\mu\le1$ と書ける。$P$ が線分 $OQ$ 上にあれば $\overrightarrow{OP}=\lambda\,\overrightarrow{OQ}$、$0\le\lambda\le1$ と書ける。よって
$$ \overrightarrow{OP}=\lambda(1-\mu)\vec a+\lambda\mu\,\vec b $$
であり、$s=\lambda(1-\mu)\ge0$、$t=\lambda\mu\ge0$、$s+t=\lambda\le1$ である。$P$ は $T$ の点である。$\square$

大学数学で見る：3 つの半平面の共通部分

方針：1 と 3 が一致することを示す。prop-ccr-halfplane により、斜交座標の 1 次不等式は半平面を表す。3 本の辺の直線を斜交座標の式で書き、どちらの側かを頂点の座標で決める。
段 1（直線 $OA$）。$t=0$ を満たす点の全体は、prop-ccr-halfplane により 1 本の直線である。$O$（斜交座標 $(0,0)$）と $A$（$(1,0)$）はこの上にあるので、これは直線 $OA$ である。$t\ge0$ と $t\le0$（つまり $-t\ge0$）は、prop-ccr-halfplane によりどちらもこの直線とその片側であり、2 つの共通部分は直線 $t=0$ だけなので、違う側である。よって、この直線の両側は $t>0$ の側と $t<0$ の側で、$B$（$(0,1)$）は $t=1>0$ の側にある。よって「直線 $OA$ に関して $B$ と同じ側（直線上を含む）」は $t\ge0$ である。
段 2（直線 $OB$）。同じように、$s=0$ は $O$ と $B$ を通る直線 $OB$ であり、$A$ は $s=1>0$ の側にある。よって「直線 $OB$ に関して $A$ と同じ側」は $s\ge0$ である。
段 3（直線 $AB$）。$s+t=1$ は $A$（$1+0=1$）と $B$（$0+1=1$）を通る直線 $AB$ である。$O$ は $s+t=0<1$ の側にある。よって「直線 $AB$ に関して $O$ と同じ側」は $s+t\le1$ である。
段 4（まとめ）。3 の共通部分は、$t\ge0$、$s\ge0$、$s+t\le1$ を同時に満たす点の全体、つまり $T$ である。$\square$

!FORMULA[369][925975646][0] の点は、!FORMULA[370][245941696][0]、!FORMULA[371][-47461280][0] を結ぶ線分 !FORMULA[372][-1304493313][0] になる。!FORMULA[373][37949][0] を !FORMULA[374][36120][0] から !FORMULA[375][36151][0] まで動かすと、線分が辺 !FORMULA[376][1137023][0] に平行に動いて三角形 !FORMULA[377][35664792][0] を塗りつぶすことを見る図。 $s+t=k$ の点は、$\overrightarrow{OA_k}=k\vec a$、$\overrightarrow{OB_k}=k\vec b$ を結ぶ線分 $A_kB_k$ になる。$k$ を $0$ から $1$ まで動かすと、線分が辺 $AB$ に平行に動いて三角形 $OAB$ を塗りつぶすことを見る図。
prf-ccr-triangle-hs は、高校の教科書の解き方と同じである。「$s+t=k$ とおいて $k$ で割る」という操作は、係数の和を $1$ にそろえて、位置ベクトルと内分点 の直線の条件を使えるようにするためのものである。prf-ccr-triangle-univ は、三角形を不等式で表された領域とみる。同じ見方は 不等式の表す領域と線形計画法 で、1 次式の最大・最小を求めるのに使う。
thm-ccr-triangle は「周と内部」をまとめて扱っている。周の上の点と内部の点を分けるには、次のように見る。

周の上の点と内部の点

三角形 $OAB$ の周は 3 辺 $OA$、$OB$、$AB$ からなる。位置ベクトルと内分点 の「直線上にある条件」の 2 により、辺 $OA$ は $s\vec a$（$0\le s\le1$）の点、辺 $OB$ は $t\vec b$（$0\le t\le1$）の点、辺 $AB$ は $s\vec a+t\vec b$（$s,t\ge0$、$s+t=1$）の点の全体である。斜交座標はただ 1 つなので、$T$ の点のうち、辺 $OA$ 上の点は $t=0$ の点、辺 $OB$ 上の点は $s=0$ の点、辺 $AB$ 上の点は $s+t=1$ の点である。
したがって、$T$ の点が周の上にあるのは、3 つの不等式 $s\ge0$、$t\ge0$、$s+t\le1$ のどれかが等号になるときである。$s>0$、$t>0$、$s+t<1$ の点は周の上になく、三角形 $OAB$ の内部にある。凸結合 $\alpha A+\beta B+\gamma C$（cor-ccr-triangle-convex）で言えば、$\alpha=1-\beta-\gamma$ なので、係数 $\alpha$、$\beta$、$\gamma$ がすべて正の点が内部の点である。

三角形の中の点と外の点

$\vec a=(4,0)$、$\vec b=(1,2)$ とする。

  1. $s=\frac13$、$t=\frac13$：$s>0$、$t>0$、$s+t=\frac23<1$ なので三角形 $OAB$ の内部の点で（rem-ccr-interior）、$P\left(\frac53,\frac23\right)$ である。これは三角形 $OAB$ の重心 $\frac{\vec 0+\vec a+\vec b}{3}$ である。prf-ccr-triangle-hs の段 1 で $k=\frac23$ とすると、$\overrightarrow{OQ}=\frac12\vec a+\frac12\vec b$ で、$Q$ は辺 $AB$ の中点、$P$ は中線 $OQ$ を $2:1$ に内分する点である。
  2. $s=\frac34$、$t=\frac12$：$s+t=\frac54>1$ なので三角形の外の点で、$P(3+\frac12,\ 1)=\left(\frac72,1\right)$ である。ex-ccr-halfplane の不等式で確かめると、$2\cdot\frac72+3\cdot1=10>8$ で、確かに $2x+3y\le8$ を満たさない。

凸結合

thm-ccr-triangle の点 $P$ は、$r=1-s-t$ とおくと
$$ \overrightarrow{OP}=r\cdot\vec 0+s\vec a+t\vec b,\qquad r\ge0,\ s\ge0,\ t\ge0,\ r+s+t=1 $$
と書ける。$\vec 0=\overrightarrow{OO}$ なので、これは 3 点 $O$、$A$、$B$ を、$0$ 以上で和が $1$ の係数で結んだ形である。

点の凸結合

点 $A_1,\dots,A_k$ と、$0$ 以上で和が $1$ の実数 $r_1,\dots,r_k$（$r_i\ge0$、$r_1+\dots+r_k=1$）をとる。基準の点 $O$ を 1 つ決めて
$$ \overrightarrow{OP}=r_1\overrightarrow{OA_1}+\dots+r_k\overrightarrow{OA_k} $$
で定まる点 $P$ を、点 $A_1,\dots,A_k$ の 凸結合 という。係数の和が $1$ なので、$P$ は基準の点 $O$ の選び方によらない（位置ベクトルと内分点 の「係数の和が 1 なら原点によらない」）。そこで $P=r_1A_1+\dots+r_kA_k$ とも書く。

凸結合は、係数を「重み」とする重み付きの平均である。2 点の凸結合 $(1-t)A+tB$（$0\le t\le1$）は線分 $AB$ 上の点であり（位置ベクトルと内分点 の「直線上にある条件」の 2）、すべての係数が $\frac1k$ の凸結合は $k$ 点の重心である。

凸結合の計算

$A(1,4)$、$B(7,1)$、$C(4,7)$ とする。

  1. $\frac13A+\frac13B+\frac13C=(4,4)$ は三角形 $ABC$ の重心である。
  2. $\frac12A+\frac12B+0\cdot C=\left(4,\frac52\right)$ は辺 $AB$ の中点で、三角形の周の上にある。
  3. $\frac12A+\frac14B+\frac14C=\left(\frac12+\frac74+1,\ 2+\frac14+\frac74\right)=\left(\frac{13}4,\ 4\right)$ は、係数 $\frac12$、$\frac14$、$\frac14$ がすべて正なので、三角形の内部の点である（rem-ccr-interior）。

thm-ccr-triangle は基準の点を頂点 $O$ にとっていた。凸結合で書くと、基準の点をどこにとっても使える形になる。

三角形の周と内部は 3 頂点の凸結合の全体

三角形 $ABC$ の周と内部は、3 点 $A$、$B$、$C$ の凸結合 $\alpha A+\beta B+\gamma C$（$\alpha,\beta,\gamma\ge0$、$\alpha+\beta+\gamma=1$）の全体に等しい。

頂点 $A$ を基準の点にする

方針：凸結合は基準の点によらないので、基準の点を $A$ にとって thm-ccr-triangle を使う。
段 1（$A$ を基準にする）。$P=\alpha A+\beta B+\gamma C$ を、基準の点を $A$ にして書くと、$\overrightarrow{AA}=\vec 0$ なので
$$ \overrightarrow{AP}=\beta\,\overrightarrow{AB}+\gamma\,\overrightarrow{AC} $$
である。
段 2（条件の言い換え）。$\alpha=1-\beta-\gamma$ なので、「$\alpha,\beta,\gamma\ge0$、$\alpha+\beta+\gamma=1$」は「$\beta\ge0$、$\gamma\ge0$、$\beta+\gamma\le1$」と同じである。
段 3（主定理を使う）。thm-ccr-triangle を、$O$ を $A$ に、$\vec a$、$\vec b$ を $\overrightarrow{AB}$、$\overrightarrow{AC}$ に替えて使うと、段 1・段 2 の点 $P$ の全体は三角形 $ABC$ の周と内部である。$\square$

空間では四面体

空間でも同じことが成り立つ。$O$、$A$、$B$、$C$ が同じ平面上にないとき（空間ベクトルと1次独立）、$\overrightarrow{OP}=s\vec a+t\vec b+u\vec c$ で $s,t,u\ge0$、$s+t+u\le1$ を満たす点の全体は、四面体 $OABC$ の表面と内部である。証明は prf-ccr-triangle-hs と同じ流れ（$s+t+u=k$ とおいて $k$ で割ると、三角形 $ABC$ の周と内部の点が現れる）なので、この記事では書かない。

条件を変えた存在範囲

prop-ccr-halfplane により、$s$、$t$ の 1 次の等式・不等式で表された存在範囲は、斜交座標の $st$ 平面で同じ条件の範囲を描き、それを格子ごと斜めにゆがめたものになる。直線は直線に、半平面は半平面に、多角形は多角形に移り、多角形の頂点は $st$ 平面の頂点 $(s,t)$ に対応する点 $s\vec a+t\vec b$ に移る。
面積も一定の倍率で変わる。$(s,t)$ を点 $s\vec a+t\vec b$ に移す対応は、$\vec a$、$\vec b$ を列に並べた行列の 1次変換 で、その行列式が lem-ccr-solve の $D$ である。1次変換と行列式：面積の拡大率 により、存在範囲の面積は、$st$ 平面での面積の $|D|$ 倍である。

面積の倍率を確かめる

$\vec a=(4,0)$、$\vec b=(1,2)$ では $D=4\cdot2-0\cdot1=8$ なので、$|D|=8$ である。

  1. $st$ 平面の三角形 $(0,0)$、$(1,0)$、$(0,1)$ の面積は $\frac12$ である。
  2. 対応する三角形 $OAB$ の面積は、倍率から $\frac12\times8=4$ のはずである。
  3. 直接計算すると、三角形 $OAB$ は底辺 $OA=4$、高さ $2$（$B$ の $y$ 座標）なので、面積は $\frac12\times4\times2=4$ で、2 と一致する。
いろいろな条件の存在範囲

$\vec a=(4,0)$、$\vec b=(1,2)$、$\overrightarrow{OP}=s\vec a+t\vec b$ とする（図3）。

  1. $s\ge0$、$t\ge0$、$s+2t\le2$：両辺を $2$ で割ると $\frac s2+t\le1$ である。$s'=\frac s2$ とおくと $\overrightarrow{OP}=s'(2\vec a)+t\vec b$、$s'\ge0$、$t\ge0$、$s'+t\le1$ なので、thm-ccr-triangle により範囲は $O$、$A'(2\vec a)=(8,0)$、$B(1,2)$ を頂点とする三角形の周と内部である。$st$ 平面での頂点 $(0,0)$、$(2,0)$、$(0,1)$ が、$O$、$A'$、$B$ に対応する。面積は $st$ 平面の $1$ の $8$ 倍で $8$ である（底辺 $8$、高さ $2$ で確かに $8$）。
  2. $s\ge0$、$t\ge0$、$1\le s+t\le2$：$s+t\le2$ の部分は $O$、$2\vec a$、$2\vec b$ の三角形で、そこから $s+t<1$ の部分（三角形 $OAB$ から辺 $AB$ を除いたもの）を取り除く。範囲は $A(4,0)$、$(8,0)$、$(2,4)$、$B(1,2)$ を頂点とする台形の周と内部である。$st$ 平面での面積は $2-\frac12=\frac32$ なので、面積は $\frac32\times8=12$ である。
  3. $0\le s\le1$、$0\le t\le1$：範囲は $O$、$A$、$C(5,2)$、$B$ を頂点とする平行四辺形 $OACB$ の周と内部である（$\overrightarrow{OC}=\vec a+\vec b$）。面積は $1\times8=8$ である。
  4. $s\ge0$、$t\ge0$ だけ：範囲は、半直線 $OA$ と半直線 $OB$ ではさまれた角の部分（周を含む）で、有界でない。
  5. $2s+3t=6$（$s$、$t$ の符号の条件なし）：$st$ 平面の直線で、$(3,0)$ と $(0,2)$ を通る。範囲は $3\vec a=(12,0)$ と $2\vec b=(2,4)$ を通る直線である。lem-ccr-solve の式を入れると $2\cdot\frac{2x-y}8+3\cdot\frac y2=6$、すなわち $2x+5y=24$ で、確かに $(12,0)$ と $(2,4)$ を通る。

条件を変えたときの存在範囲。左上 !FORMULA[621][-2012146231][0]（三角形 !FORMULA[622][37081][0]、!FORMULA[623][-177189123][0]、!FORMULA[624][1837121222][0]）、右上 !FORMULA[625][1076314595][0]（台形）、左下 !FORMULA[626][-2037746044][0]（平行四辺形）、右下 !FORMULA[627][1720443191][0]（角の部分、有界でない）。!FORMULA[628][1186623][0] 平面の図形が格子ごとゆがんで移ることを見る図。 条件を変えたときの存在範囲。左上 $s+2t\le2$（三角形 $O$、$2\vec a$、$\vec b$）、右上 $1\le s+t\le2$（台形）、左下 $0\le s,t\le1$（平行四辺形）、右下 $s,t\ge0$（角の部分、有界でない）。$st$ 平面の図形が格子ごとゆがんで移ることを見る図。
1 の「$s+2t\le2$ を $\frac s2+t\le1$ に直して、$2\vec a$ を新しいベクトルとみる」操作は、係数の和を $1$ にそろえる prf-ccr-triangle-hs の考え方と同じである。

例と反例

外した仮定崩れる主張ボックス
$\vec a$、$\vec b$ が平行でない範囲は三角形、斜交座標はただ 1 つex-ccr-parallel
$s\ge0$、$t\ge0$範囲は有界な三角形ex-ccr-no-sign
不等式が等号を含む（$\le$）範囲は周を含み、1 次式の最大値があるex-ccr-strict
条件が $s$、$t$ の 1 次式範囲は凸（線分を含む）ex-ccr-nonlinear
反例：2 つのベクトルが平行なとき

$\vec a=(1,0)$、$\vec b=(2,0)$ とすると、$\vec b=2\vec a$ で平行である。$s\ge0$、$t\ge0$、$s+t\le1$ のとき $s\vec a+t\vec b=(s+2t,\ 0)$ で、$s+2t$ は $0$ から $2$ までのすべての値をとる（$s=0$、$0\le t\le1$ だけでも $0\le2t\le2$ となる）。範囲は $x$ 軸上の線分 $0\le x\le2$ で、三角形にならない（面積は $0$、$D=1\cdot0-0\cdot2=0$）。また、点 $(1,0)$ は $(s,t)=(1,0)$ からも $\left(0,\frac12\right)$ からも得られ、$(s,t)$ は点によってただ 1 つに決まらない。
満たさない性質：平行でないこと。破る主張：thm-ccr-triangle と def-ccr-oblique の「ただ 1 つ」。lem-ccr-solve の $D\ne0$ も成り立たない。

反例：符号の条件を外すと有界でない

$\vec a=(4,0)$、$\vec b=(1,2)$ で、条件を $s+t\le1$ だけにする。ex-ccr-halfplane の 3 により、範囲は $2x+3y\le8$ の半平面で、有界でない。

  1. $(s,t)=(-5,0)$ は $s+t=-5\le1$ を満たし、点は $(-20,0)$ である。$s$ を小さくすれば、点はいくらでも遠くへ行く。
  2. $(s,t)=(3,-2)$ は $s+t=1$ で、点は $(12-2,\ -4)=(10,-4)$ である。$2\cdot10+3\cdot(-4)=8$ なので直線 $AB$ 上にあるが、$t<0$ なので線分 $AB$ の外（$A$ の先）にある。
    破る主張：thm-ccr-triangle の範囲が三角形であること。prf-ccr-triangle-univ では、3 つの半平面のうち 2 つ（$s\ge0$、$t\ge0$）を使っていた。
反例：等号を除くと周が抜ける

条件を $s>0$、$t>0$、$s+t<1$ にすると、範囲は三角形 $OAB$ の内部だけで、周を含まない（周の上の点は 3 つの不等式のどれかが等号になる点だからである。rem-ccr-interior）。たとえば辺 $AB$ の中点（$s=t=\frac12$）は $s+t=1$ なので入らない。
$\vec a=(4,0)$、$\vec b=(1,2)$ で、この範囲の点の $x$ 座標 $4s+t$ を考える。$s+t<1$、$t>0$ なので $4s+t<4(1-t)+t=4-3t<4$ で、$x$ 座標はいつも $4$ より小さい。一方 $s=1-2\varepsilon$、$t=\varepsilon$（$0<\varepsilon<\frac12$）とすると範囲の点で、$x$ 座標は $4-7\varepsilon$ となり、$\varepsilon$ を小さくすればいくらでも $4$ に近づく。よって $x$ 座標には最大値がない。周を含む thm-ccr-triangle の範囲なら、最大値 $4$ を頂点 $A$ でとる（不等式の表す領域と線形計画法 の主定理）。

反例：1 次でない条件では凸にならない

条件を $s\ge0$、$t\ge0$、$\sqrt s+\sqrt t\le1$ にする（図4）。

  1. $A$（$(s,t)=(1,0)$）は $\sqrt1+\sqrt0=1\le1$ を満たし、範囲に入る。$B$（$(0,1)$）も入る。
  2. 線分 $AB$ の中点は $(s,t)=\left(\frac12,\frac12\right)$ で、$\sqrt{\frac12}+\sqrt{\frac12}=\sqrt2>1$ なので入らない。
    範囲の 2 点 $A$、$B$ を結ぶ線分が範囲からはみ出すので、この範囲は 凸集合 でない。$\sqrt s+\sqrt t\le1$ は $s$、$t$ の 1 次不等式でないので、prop-ccr-halfplane が使えない。破る性質：1 次不等式の共通部分はいつも凸である（不等式の表す領域と線形計画法）。

!FORMULA[722][182823480][0] の範囲。左は !FORMULA[723][1186623][0] 平面、右は点 !FORMULA[724][37112][0] の範囲。!FORMULA[725][36647][0] と !FORMULA[726][36678][0] は入るが、線分 !FORMULA[727][1137023][0] の中点は入らない（凸でない）ことを見る図。 $\sqrt s+\sqrt t\le1$ の範囲。左は $st$ 平面、右は点 $P$ の範囲。$A$ と $B$ は入るが、線分 $AB$ の中点は入らない（凸でない）ことを見る図。

高校数学で解く・大学数学で見る：凸包・単体・錐

高校数学では、点の存在範囲を「係数の条件 → 斜交座標の図 → ゆがめた図」の順に求めた。大学数学では、どんな点の集まりにも「凸結合の全体」を考え、名前を付けて調べる。

高校数学で解く大学数学で見る
$s\ge0$、$t\ge0$、$s+t\le1$三角形 $OAB$ の周と内部3 点の凸包、2 次元の単体
$s,t,u\ge0$、$s+t+u\le1$四面体 $OABC$ の表面と内部3 次元の単体
$s\ge0$、$t\ge0$角の部分凸錐
$s+t=k$ で割る線分を動かして塗る凸結合の全体は凸（prop-ccr-hull-convex）
有限個の点の凸包

点 $A_1,\dots,A_k$ の凸結合（def-ccr-convex）の全体を、$A_1,\dots,A_k$ の 凸包 という。この定義は BV04 の §2.1.4（p. 24）による。

cor-ccr-triangle-convex は、「一直線上にない 3 点の凸包は三角形の周と内部である」と言い換えられる。

凸包は凸

点 $A_1,\dots,A_k$ の凸包を $K$ とする。$K$ の 2 点 $P$、$Q$ と $0\le\lambda\le1$ に対し、点 $(1-\lambda)P+\lambda Q$ も $K$ に属する。つまり、$K$ の 2 点を結ぶ線分は $K$ に含まれる。

2 つの凸結合を混ぜる

方針：$P$、$Q$ をそれぞれ凸結合で書き、混ぜた点の係数が $0$ 以上で和が $1$ であることを確かめる。
段 1（書き出す）。$P=\sum_{i=1}^k r_iA_i$、$Q=\sum_{i=1}^k r'_iA_i$（$r_i,r'_i\ge0$、$\sum r_i=\sum r'_i=1$）とする。基準の点 $O$ を決めると
$$ (1-\lambda)\overrightarrow{OP}+\lambda\overrightarrow{OQ}=\sum_{i=1}^k\bigl((1-\lambda)r_i+\lambda r'_i\bigr)\overrightarrow{OA_i} $$
である。
段 2（係数を調べる）。$1-\lambda\ge0$、$\lambda\ge0$、$r_i\ge0$、$r'_i\ge0$ なので、係数 $(1-\lambda)r_i+\lambda r'_i$ は $0$ 以上である。その和は $(1-\lambda)\sum r_i+\lambda\sum r'_i=(1-\lambda)+\lambda=1$ である。よって $(1-\lambda)P+\lambda Q$ は $A_1,\dots,A_k$ の凸結合で、$K$ に属する。$\square$

2 点を結ぶ線分をいつも含む図形を 凸集合 という。prop-ccr-hull-convex は、凸包が凸集合であることを言っている。さらに凸包は、$A_1,\dots,A_k$ を含む凸集合のうちで最小のものである（BV04 の §2.1.4。大学向けの証明は 凸集合 にある）。

4 点の凸包
  1. $A(0,0)$、$B(4,0)$、$C(4,4)$、$D(0,4)$ の凸包は、正方形 $ABCD$ の周と内部である。たとえば中心 $(2,2)$ は $\frac14A+\frac14B+\frac14C+\frac14D$ である。
  2. $A(0,0)$、$B(4,0)$、$D(0,4)$、$E(1,1)$ の凸包は、三角形 $ABD$ の周と内部である。$E$ は $E=\frac12A+\frac14B+\frac14D$（$\frac14(4,0)+\frac14(0,4)=(1,1)$）と $A$、$B$、$D$ の凸結合で書けるので、$E$ を加えても凸包は広がらない。凸包の「角」になるのは $A$、$B$、$D$ だけである。
単体と錐
  1. 単体。同じ直線上にない 3 点の凸包（三角形）を 2 次元の 単体、同じ平面上にない 4 点の凸包（四面体）を 3 次元の単体という。2 点の凸包（線分）は 1 次元の単体である。特に $s\ge0$、$t\ge0$、$s+t\le1$ を満たす $(s,t)$ の全体は、$(0,0)$、$(1,0)$、$(0,1)$ の凸包で、BV04 は Example 2.5（p. 33）でこれを単位単体とよぶ。
  2. 確率としての見方。3 つの数 $r_1,r_2,r_3$ が $0$ 以上で和が $1$ なら、3 つのことがらの確率の組とみなせる。この組の全体も単体であり（BV04 の Example 2.5 の probability simplex）、凸結合 $r_1A_1+r_2A_2+r_3A_3$ は、確率 $r_i$ で点 $A_i$ を選ぶときの位置の 期待値 である。
  3. 錐。$s\ge0$、$t\ge0$ だけを課した $s\vec a+t\vec b$ の全体（ex-ccr-regions の 4）は、$0$ 以上の実数倍しても外に出ない凸集合で、凸錐 という（BV04 の §2.1.5、p. 25）。

さらに先へ

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する

Mathpediaを支援する
点の存在範囲と凸結合