凸多面体(convex polytope)とは、$\mathbb{R}^n$ の空でない有限集合の凸包のことであり、空でない有界な多面体と同じものである。凸多面体を片側に含む超平面との交わりを面といい、面は頂点の部分集合の凸包で有限個しかなく、面の面と 2 つの面の共通部分はまた面なので、面の全体は包含について有限の束(面束)になる。原点を内部に含む凸多面体 $P$ の極双対 $P^\circ=\{y\mid x\cdot y\le1\ (x\in P)\}$ はまた凸多面体で $(P^\circ)^\circ=P$ を満たし、面の対応 $F\mapsto F^\diamond$ は包含を逆にする面束の全単射で、空でも全体でもない面では次元の和が $n-1$ になる。立方体と正八面体は互いの極双対である。
凸多面体(convex polytope)とは、$\mathbb{R}^n$ の有限個の点の凸包のことである。三角形・正方形などの凸多角形、立方体・正四面体・正八面体などの凸な立体がその例であり、次元を 3 に限らず、$n$ 次元の立方体 $[-1,1]^n$ や単体も含む。有限個の 1 次不等式の解の全体(多面体)で空でなく有界なものとちょうど一致すること(Minkowski–Weyl の定理)が知られており、凸多面体は「有限個の頂点」と「有限個の不等式」の 2 通りの言葉で扱える。
立方体には頂点・辺・正方形の面があり、辺は 2 つの頂点を含み、正方形の面は 4 本の辺を含む。このような包含関係の全体を 面束 という。この記事では、凸多面体の面の基本性質(面は頂点の凸包、面の面は面、面の共通部分は面)を証明して面束が有限の束になることを示し、主定理として、原点を内部に含む凸多面体の 極双対 が面束を上下逆にすること(面の次元の和が $n-1$ になる対応)を証明する。立方体と正八面体はこの意味で互いに双対であり、立方体の $k$ 次元の面の個数から正八面体の面の個数が読み取れる。
以下、$\mathbb{R}^n$ に標準内積 $x\cdot y$ とノルム $\lvert x\rvert$ を入れる。集合 $S$ のアフィン包の次元を $\dim S$ と書き、$\dim\emptyset:=-1$ とする。
空でない有限集合 $V\subset\mathbb{R}^n$ の凸包 $P=\operatorname{conv}V$ を 凸多面体 という。$\dim P=d$ のとき $P$ を $d$ 次元凸多面体という。$c\in\mathbb{R}^n$ と $\delta\in\mathbb{R}$ が「すべての $x\in P$ について $c\cdot x\le\delta$」を満たすとき、
$$
F=P\cap\{x\mid c\cdot x=\delta\}
$$
を $P$ の 面 という。$0$ 次元の面(1 点)を 頂点、$1$ 次元の面を 辺、$(\dim P-1)$ 次元の面を ファセット という。$P$ の面の全体を包含で順序づけた集合 $\mathcal{L}(P)$ を $P$ の 面束 といい、$k$ 次元の面の個数を $f_k(P)$ と書く。
$c=0$ にとると、$\delta=0$ で $F=P$、$\delta=1$ で $F=\emptyset$ となるので、$P$ 自身と空集合も面である。面の定義は 多面体 の定義「面・頂点・辺・ファセット」と同じであり、凸多面体・面・次元・ファセットの用語は BR15 §2.1 にもある。面束の名前と定義は BR15 §5.1 による。
空でない有界な 多面体(有限個の閉半空間の共通部分)は有限個の点の凸包であり、逆も成り立つ(多面体 の定理「Minkowski–Weylの定理(凸多面体の場合)」)。したがって凸多面体は空でない有界な多面体と同じものであり(多面体 の記事は空集合も凸多面体に数えるが、この記事では数えない)、頂点は端点と同じもので(多面体 の定理「頂点の特徴づけ」)、$P=\operatorname{conv}V$ ならすべての頂点は $V$ に属し、$P$ は頂点全体の凸包に等しい。以下、$P$ の頂点の全体を $\operatorname{vert}P$ と書く。頂点の存在と求め方、不等式による記述との行き来は 多面体 の記事が扱い、この記事は面どうしの関係と双対性を扱う。
$P$ を凸多面体とし、$V:=\operatorname{vert}P$ とする。
3 は BR15 の Exercise 2.5 に問題として挙げられている。
$\mathcal{L}(P)$ は最小元 $\emptyset$ と最大元 $P$ をもつ有限の束である。2 つの面 $F,G$ の下限は $F\cap G$、上限は $F\cup G$ を含む面すべての共通部分である。$\mathcal{L}(P)$ の真に増大する列 $F_0\subsetneq F_1\subsetneq\dots\subsetneq F_r$ は $r\le\dim P+1$ を満たす。
有限性は thm-cpt-faces の 1、下限は 2 による。$F\cup G$ を含む面は $P$ を含めて少なくとも 1 つあり、有限個なので、その共通部分は 2 により面で、$F$ と $G$ を含む面のうち最小である。列については、4 により $\dim F_0< \dots< \dim F_r$ で、$-1\le\dim F_0$、$\dim F_r\le\dim P$ だからである。$\square$
$v_0,\dots,v_d\in\mathbb{R}^n$ がアフィン独立のとき、$\Delta:=\operatorname{conv}\{v_0,\dots,v_d\}$ を $d$ 次元 単体 という。$\{0,\dots,d\}$ の各部分集合 $W$ について $\operatorname{conv}\{v_i\mid i\in W\}$ は $\Delta$ の面であり、$\Delta$ の面はこれで尽きる。したがって $f_k(\Delta)=\binom{d+1}{k+1}$ で、面束は $\{0,\dots,d\}$ の部分集合全体の束(Boolean 束)と同型である(BR15 Exercise 2.6 と §5.1)。
アフィン独立性から $(v_i,1)\in\mathbb{R}^{n+1}$($i=0,\dots,d$)は 1 次独立なので、連立 1 次方程式 $c\cdot v_i-\delta=b_i$($i=0,\dots,d$)は任意の $b$ について解 $(c,\delta)$ をもつ。$b_i=0$($i\in W$)、$b_i=-1$($i\notin W$)として解くと、$x=\sum_i\lambda_iv_i\in\Delta$ について $c\cdot x-\delta=-\sum_{i\notin W}\lambda_i\le0$ で、等号は $i\notin W$ で $\lambda_i=0$ のとき、すなわち $x\in\operatorname{conv}\{v_i\mid i\in W\}$ のときに限る。逆に thm-cpt-faces の 1 により、どの面も頂点の部分集合の凸包である。アフィン独立な点の集合ではどの点も残りの点の凸包に入らないので、$W$ が異なれば面の頂点の集合も異なり、面は異なる。$\lvert W\rvert=k+1$ の面の次元は $k$ である。
$Q_n:=[-1,1]^n=\operatorname{conv}\{-1,1\}^n$ の面は、空集合と、$s\in\{-1,0,1\}^n$ ごとの
$$
F_s:=\{x\in Q_n\mid s_i\ne0\text{ となる }i\text{ では }x_i=s_i\}
$$
である。$F_s$ の次元は $s$ の成分のうち $0$ であるものの個数 $k$ に等しく、$f_k(Q_n)=\binom nk2^{n-k}$($0\le k\le n$)である。$n=3$ では頂点 $8$、辺 $12$、正方形の面 $6$ である。この分類と個数は 立方体と直方体 の定理「立方体の面」で証明されている(そこでは $Q_n$ を $K_n$、$F_s$ を $F(J,\varepsilon)$、$J=\{i\mid s_i=0\}$ と書く)。
$P\subset\mathbb{R}^n$ を凸多面体とする。
$$
P^\circ:=\{y\in\mathbb{R}^n\mid\text{すべての }x\in P\text{ について }x\cdot y\le1\}
$$
を $P$ の 極双対(polar dual)という。$P$ の面 $F$ に対し、$P^\circ$ の部分集合
$$
F^\diamond:=\{y\in P^\circ\mid\text{すべての }x\in F\text{ について }x\cdot y=1\}
$$
を $F$ の 双対の面 という。$P^\circ$ の面 $G$ に対しても同様に $G^\diamond:=\{x\in P\mid\text{すべての }y\in G\text{ について }x\cdot y=1\}$ と定める。
$P^\circ$ は一般の集合の極集合(双極定理 の定義「極集合と前極集合」)を凸多面体に当てはめたもので、凸多面体の極双対は BR15 の第 4 章末の注 5 と Exercise 5.9 で定義されている。正方形 $[-1,1]^2$ の極双対が菱形 $\{\lvert y_1\rvert+\lvert y_2\rvert\le1\}$ になることは 双極定理 の例「正方形と菱形」にある。
$P\subset\mathbb{R}^n$ を凸多面体で、原点を内部に含むものとし、$V:=\operatorname{vert}P$ とする。
原点が内部の点なので、$\varepsilon>0$ で閉球 $\{\lvert x\rvert\le\varepsilon\}$ が $P$ に含まれるものがある。
2 は「$P^\circ$ の面束は $P$ の面束を上下逆にしたものである」という主張で、BR15 の Exercise 5.9 (a) に問題として挙げられている。3 の次元の関係は 2 から直接は出ないので、別に示した。
thm-cpt-polar の仮定のもとで、$0\le k\le n-1$ について $f_k(P^\circ)=f_{n-1-k}(P)$ である。とくに $P^\circ$ の頂点は $P$ のファセットと、$P^\circ$ のファセットは $P$ の頂点と一対一に対応する。
$\dim P=n$ なので、空でも $P$ でもない面の次元は $0$ から $n-1$ の間にある。thm-cpt-polar の 2・3 により、$k$ 次元の面と $P^\circ$ の $(n-1-k)$ 次元の面は $F\mapsto F^\diamond$ で一対一に対応する。$\square$
立方体 $Q_n=\operatorname{conv}\{-1,1\}^n$ について、$\max_{\varepsilon\in\{\pm1\}^n}\varepsilon\cdot y=\sum_i\lvert y_i\rvert$ なので、thm-cpt-polar の 1 から
$$
Q_n^\circ=O_n:=\Bigl\{y\Bigm|\sum_i\lvert y_i\rvert\le1\Bigr\}=\operatorname{conv}\{\pm e_1,\dots,\pm e_n\}
$$
($n$ 次元の正軸体、cross-polytope。$n=3$ が正八面体)である。最後の等号は 多面体 の例「立方体の頂点」で確かめられている。ex-cpt-cube の面 $F_s$($s\ne0$、$T:=\{i\mid s_i\ne0\}$)の双対の面は
$$
F_s^\diamond=\operatorname{conv}\{s_ie_i\mid i\in T\}
$$
で、次元は $\lvert T\rvert-1=n-1-\dim F_s$ である。cor-cpt-fvector と ex-cpt-cube から $f_j(O_n)=f_{n-1-j}(Q_n)=\binom{n}{j+1}2^{j+1}$($0\le j\le n-1$)であり、$n=3$ の正八面体は頂点 $6$、辺 $12$、三角形の面 $8$ をもつ。
$F_s$ の頂点は、$i\in T$ で $\varepsilon_i=s_i$ となる $\varepsilon\in\{\pm1\}^n$ である。$y\in O_n$ について $\varepsilon\cdot y\le\sum_i\lvert y_i\rvert\le1$ で、$\varepsilon\cdot y=1$ はすべての $i$ で $\varepsilon_iy_i=\lvert y_i\rvert$ かつ $\sum_i\lvert y_i\rvert=1$ のときに限る。$i\notin T$ では $\varepsilon_i$ が $\pm1$ の両方をとるので $y_i=0$、$i\in T$ では $s_iy_i=\lvert y_i\rvert\ge0$ である。よって $F_s^\diamond=\{\sum_{i\in T}\mu_is_ie_i\mid\mu_i\ge0,\ \sum_i\mu_i=1\}$。
$v_1=(1,1,1)$、$v_2=(1,-1,-1)$、$v_3=(-1,1,-1)$、$v_4=(-1,-1,1)$ の凸包 $T$ は正四面体で、原点を内部に含み、$T=\{x\mid(-v_i)\cdot x\le1\ (i=1,\dots,4)\}$ である(多面体 の例「正四面体」)。thm-cpt-polar の 1 により $T^\circ=\{y\mid v_i\cdot y\le1\}=-T$ であり、$T^\circ$ も正四面体である。頂点 $v_1$ の双対の面は $\{y\in-T\mid v_1\cdot y=1\}=\operatorname{conv}\{-v_2,-v_3,-v_4\}$ で、$-T$ の頂点 $-v_1$ の向かいのファセットである($i\ne1$ なら $v_1\cdot v_i=-1$、$v_1\cdot v_1=3$)。
thm-cpt-polar の仮定を 1 つずつ外すと、次のように結論が成り立たない。
| 外す条件 | 例 | 成り立たなくなること |
|---|---|---|
| 原点が $P$ の内部にある | $P=[0,1]^2$(原点は頂点) | $P^\circ$ は凸多面体(1) |
| 原点が $P$ の内部にある | $P=[1,2]\subset\mathbb{R}$ | $(P^\circ)^\circ=P$(1) |
| $P$ は有界 | 半平面 $P=\{x\in\mathbb{R}^2\mid x_1\ge-1\}$ | $F\mapsto F^\diamond$ は全単射(2) |
| $P$ は有限個の点の凸包 | 閉単位円板 $D\subset\mathbb{R}^2$ | $P^\circ$ は凸多面体(1) |
どの行も、表の左の条件だけを外している。
1 行目:$P=[0,1]^2$ は凸多面体だが、原点は内部にない。$y=(-t,-t)$($t\ge0$)は $x\in P$ で $x\cdot y\le0\le1$ を満たすので $P^\circ$ に属し、$P^\circ$ は有界でなく、凸多面体でない。
2 行目:$P=[1,2]$ は凸多面体で原点を含まない。$xy\le1$($1\le x\le2$)は $y\le1/2$ と同値なので $P^\circ=(-\infty,1/2]$、さらに $xy\le1$($y\le1/2$)は $0\le x\le2$ と同値なので $(P^\circ)^\circ=[0,2]\ne P$ である。
3 行目:$P$ は多面体で原点を内部に含むが有界でない。$P$ 上で $c\cdot x\le\delta$ となる $c$ は $c=(-t,0)$($t\ge0$)の形で、$t>0$ なら $\delta\ge t$ が必要であり、面は $\emptyset$、直線 $\{x_1=-1\}$、$P$ の 3 つである。一方 $P^\circ=\{(y_1,0)\mid-1\le y_1\le0\}$ は線分で($x_2$ が自由なので $y_2=0$、$x_1\to\infty$ から $y_1\le0$、$x_1=-1$ から $y_1\ge-1$)、面は $\emptyset$、2 つの端点、線分自身の 4 つである。個数が違うので全単射はない。
4 行目:$D$ はコンパクト凸集合で原点を内部に含むが、有限個の点の凸包ではない(多面体 の反例の表の 2 行目)。$\lvert x\rvert\le1$ での $x\cdot y$ の最大値は $\lvert y\rvert$ なので $D^\circ=D$ であり、凸多面体でない。
3 次元の場合。$n=3$ で原点を内部に含む凸多面体では(このとき $\dim P=3$ である)、cor-cpt-fvector により $P^\circ$ の頂点・辺・面の数は $P$ の面・辺・頂点の数になり、Euler の関係 $f_0-f_1+f_2=2$(Eulerの多面体定理)は双対をとっても同じ形を保つ。
単純と単体的。どの頂点もちょうど $\dim P$ 本の辺に含まれる凸多面体を単純、すべての真の面が単体である凸多面体を単体的という。原点を内部に含む凸多面体 $P$ について、$P$ が単純であることと $P^\circ$ が単体的であることは同値である(BR15 の Exercise 5.9 (b) に問題として挙げられている。この記事では証明しない)。Dehn–Sommerville方程式 の記事は、単純な凸多面体の面の数の関係式を、極双対を通して単体的な側から見る注意を述べている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する