ISEGORIA / 数学百科事典
凸幾何：形・凸包・双対性
集合が凸であるとは、そのどの二点についても、二点を結ぶ線分がその集合に含まれることです。この一つの規則だけで、豊かな幾何学ができます。凸体は、各方向にどこまで届くか、つまり支持関数によって完全に記述されます。二つの凸体は形のままで足し合わせることができ、その支持関数はただ足し算になります。原点を含む物体にはどれも、頂点と面、角と接平面を入れ替えた極という双子があります。さらに、接していない二つの凸体は、いつも一枚の平面で引き離すことができ、最も広い隙間の幅は二つの間の最短距離に等しくなります。これらの事実は、線形計画、最大マージン分類器、ゲームの衝突判定、等周不等式の土台にあります。三つの実験では、極双対性を 3 次元で分解して見せ、形を足し合わせて届く距離が足し算になるのを確かめ、二つの多面体の最短距離を計算します。
前提知識: 平面と空間のベクトルと内積、面積と体積、集合の上での関数の最大値
予想してから操作し、各実験の練習問題で理解を確かめてください。練習問題は三つの難易度で毎回新しく生成されます。グラフは数式の図示であり、証明ではありません。
1. 極双対性：すべての点が接平面
原点を含む凸体 \(K\) の極 \(K^\circ\) とは、\(K\) のすべての \(x\) について \(\langle x,y\rangle\le1\) となる \(y\) の全体です。それぞれの \(y\) は平面 \(\langle x,y\rangle=1\) を表し、この平面は \(K\) の内部を通りません。\(y\) が \(K^\circ\) の境界に近いほど、その平面は \(K\) に触れそうになります。ノルムの単位球の極は双対ノルムの単位球なので、\(\ell_p\) 球の極は \(1/p+1/q=1\) を満たす \(\ell_q\) 球です。\(s=1/p\) を立方体（\(p=\infty\)）から球（\(p=2\)）、正八面体（\(p=1\)）まで動かして、二つの物体が入れ替わるのを見てください。\(K\) を \(c\) 倍すると \(K^\circ\) は \(1/c\) 倍になるので、積 \(\mathrm{vol}K\cdot\mathrm{vol}K^\circ\)（マーラーの体積積）は形だけで決まります。この値は立方体と正八面体で最小、球で最大になります。
計算例. 立方体 \([-1,1]^3\) の体積は 8、その極である正八面体 \(|y_1|+|y_2|+|y_3|\le1\) の体積は \(4/3\) なので、積は \(32/3=10.67\) です。球と、その自分自身である極の積は \((4\pi/3)^2=17.55\) です。その中間の \(p=3\)、\(q=3/2\) では、体積は \(8\Gamma(4/3)^3=5.696\) と \(8\Gamma(5/3)^3/2=2.943\) で、積は 16.76 です。\(p=3\) のとき、\(K^\circ\) の点 \(y=3^{-2/3}(1,1,1)\) をとります。これは平面 \(x_1+x_2+x_3=3^{2/3}=2.080\) を表し、中心からの距離は \(1/|y|=3^{1/6}=1.201\) です。この平面は \(K\) に \(x^*=3^{-1/3}(1,1,1)=(0.693,0.693,0.693)\) で接し、そこでは \(\langle x^*,y\rangle=1\) です。
注意点. 公式と \(\ell_p\) 球の極の関係は \(1\le p\le\infty\) で成り立つので、\(s\) は \([0,1]\) に限っています。立方体と正八面体では、曲面を細かい格子から描いているため、辺がごくわずかに丸く見えます。点対称な凸体の体積積がつねに \(32/3\) 以上になるというのがマーラー予想で、2 次元と 3 次元で証明されており（3 次元は 2020 年に入江と柴田）、4 次元以上は未解決です。上からの評価はブラシュケ・サンタロの不等式で、等号は楕円体のときに限ります。
立方体の極が正八面体になり、立方体の 6 つの面の代わりに 6 つの頂点が現れるのはなぜですか？
立方体 \([-1,1]^3\) の各面は平面 \(x_i=\pm1\) にあり、これは \(y=\pm e_i\) に対する \(\langle x,y\rangle=1\) です。一つの面が極の一つの頂点を与え、合計 6 個です。立方体の 8 つの角 \(\varepsilon=(\pm1,\pm1,\pm1)\) のそれぞれは条件 \(\langle\varepsilon,y\rangle\le1\) を与え、これは極の一つの面で、合計 8 個です。こうして頂点と面が入れ替わり、辺は辺に対応して、個数 \((V,E,F)=(8,12,6)\) は \((6,12,8)\) になります。
2. ミンコフスキー和：足し算できる形
二つの集合のミンコフスキー和は \(A+B=\{a+b:a\in A,\,b\in B\}\) です。\(A\) のすべての点に \(B\) のコピーを置く、または \(A\) の縁に沿って \(B\) を滑らせて、覆ったところをすべて残す、と考えられます。方向 \(u\) への物体の届く距離、すなわち支持関数 \(h_A(u)=\max_{a\in A}\langle a,u\rangle\) は、凸体を完全に決めます。ミンコフスキー和のもとでは普通の足し算のように振る舞い、\(h_{A+B}=h_A+h_B\) です。\(B\) が半径 \(t\) の円板なら和は \(A\) の平行体で、その面積は \(A\) の面積、各辺に沿った帯、各頂点の扇形に分かれます。これがシュタイナーの公式です。ほかの \(B\) では、面積は \(t\) の二次式で、真ん中に混合面積 \(V(A,B)\) が現れます。ブルン・ミンコフスキーの不等式は、面積の平方根は、和の面積から予想されるよりつねに速く足し合わされる、と述べています。
計算例. \(A\) を正方形 \([-1,1]^2\)（面積 4、周長 8）、\(B\) を単位円板で \(t=0.5\) とします。方向 \(\theta=0\) の届く距離は \(1+0.5=1.5\) です。シュタイナーの公式から \(|A+tD|=4+8(0.5)+\pi(0.5)^2=8.785\) となり、正方形、面積 1 の帯 4 つ、合計面積 0.785 の扇形 4 つに分かれます。向きの揃った一辺 2 と一辺 1 の正方形の和は、一辺 3、面積 9 の正方形で、\(\sqrt9=3=\sqrt4+\sqrt1\) と等号が成り立ちます。この二つが相似の位置にあるからです。正三角形 \(A\) とその半回転 \(-A\) はそうではなく、\(A+(-A)\) は面積 \(6|A|\) の六角形で、比は \(\sqrt6/2=1.2247\) です。
注意点. この実験は多角形で計算しています。円板は 180 角形なので、表示するシュタイナーの面積は約 5000 分の 1 の精度でしか厳密ではありません。線分の面積はゼロなので、そのブルン・ミンコフスキー比は \(\sqrt{|A+B|/|A|}\) になります。\(|A|\) を \(h\) で表す公式は \(h\) が微分可能であることを要しますが、多角形では滑らかな区間ごとの積分として成り立ちます。図は領域を原点を中心に描いているので、どの支持関数も正になります。
ブルン・ミンコフスキーの不等式で等号が成り立つのはいつですか？
\(A\) と \(B\) が相似の位置にあるとき、つまり \(B\) が \(A\) を拡大縮小して平行移動したもの（同じ形で同じ向き）であるときに限ります。このとき \(A+B\) は \(A\) の \(1+c\) 倍で、面積は \((1+c)^2|A|\)、その平方根は \((1+c)\sqrt{|A|}=\sqrt{|A|}+\sqrt{|B|}\) です。傾きの違う二つの正方形や、正方形と円板など、ほかのどの組でも真の不等式になります。
3. 凸包と分離平面
有限個の点の凸包は、それらを含む最小の凸体で、頂点がそれらの点の一部であるような多面体であり、オイラーの関係 \(V-E+F=2\) が成り立ちます。交わらない二つの凸体は、いつも一枚の平面で分離できます。最良の平面を見つけるには、\(A\) の点 \(p\) と \(B\) の点 \(q\) の最近の組を探します。中点を通り \(q-p\) に垂直な平面は、両側に \(d/2\) の余白を残します。同じことですが、単位ベクトル \(n\) のうちで隙間 \(\min_B\langle n,x\rangle-\max_A\langle n,x\rangle\) が最大になるのは \(q-p\) の向きのときで、その値が距離 \(d\) です。方向を傾けると隙間は縮みます。最短距離と最も幅の広い分離帯は、同じ数を二つの側から見たもので、これが最大マージン分類器の背後にある幾何学です。
計算例. \(A\) を立方体 \([-1,1]^3\)、\(B\) を同じ立方体を \((3,3,3)\) だけ動かしたものとします。最近点は角 \(p=(1,1,1)\) と \(q=(2,2,2)\) なので、\(d=\sqrt3=1.732\)、\(n^*=(1,1,1)/\sqrt3\) で、分離平面は中点 \((1.5,1.5,1.5)\) を通る \(x+y+z=4.5\)、余白は両側とも \(\sqrt3/2=0.866\) です。\(x\) 軸だけで測った隙間は \(3-2=1\) にすぎません。代わりに \((3,3,0)\) だけ動かすと、鉛直な二本の辺が向き合い、\(d=\sqrt2\) です。頂点までの距離が 1.4 の正八面体を \((4,0,0)\) に置くと、立方体との距離は先端と面の間で \(d=4-1.4-1=1.6\) です。
注意点. 距離は多面体については厳密に計算しており、すべての頂点とすべての面、すべての辺とすべての辺を組み合わせて調べます。ここにある少数の点なら速いのですが、数千個の点を扱う方法ではありません。滑らかな物体では、最近の組を反復法で求めます。点群の凸包は 12 個の点から毎回計算し直しており、そのうち 3 点は飲み込まれます。物体が重なっているときは分離平面がなく、どの方向でも隙間は負になります。
最良の分離方向が、二つの物体の間の最短の線分の向きになるのはなぜですか？
\(A\) と \(B\) を分離する平面は、\(A\) の点から \(B\) の点へ向かうどの線分とも交わらなければならず、最近の組 \(p,q\) についても同じです。単位ベクトル \(n\) に沿った隙間は、コーシー・シュワルツの不等式により \(\langle n,q-p\rangle\le|q-p|=d\) 以下で、等号は \(n\) が \(q-p\) の向きのときに限ります。そしてその向きは実際に \(d\) を達成します。組が最小であることから、\(p\) と \(q\) を通り \(q-p\) に垂直な平面が、それぞれ \(A\) と \(B\) を支えるからです。したがって \(d\) は上界であり、達成もされます。