凸多面体

同義語:convex polytopepolytopeポリトープ

概要

凸多面体(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$ になる。立方体と正八面体は互いの極双対である。

$$\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}} $$

前提知識: 凸包, 多面体, 超平面

凸多面体(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$ とする。

  1. $P$ の面 $F$ は $F=\operatorname{conv}(V\cap F)$ を満たし、$F\ne\emptyset$ なら $F$ は凸多面体で $\operatorname{vert}F=V\cap F$ である。とくに $P$ の面は有限個である。
  2. $P$ の 2 つの面の共通部分は $P$ の面である。
  3. $F$ が $P$ の面で、$G$ が $F$ の面なら、$G$ は $P$ の面である。
  4. $G\subsetneq F$ が $P$ の面なら、$\dim G< \dim F$ である。
  1. $F=P\cap\{c\cdot x=\delta\}$($P$ 上で $c\cdot x\le\delta$)とする。$x\in F$ を $x=\sum_{v\in V}\lambda_vv$($\lambda_v\ge0$、$\sum_v\lambda_v=1$)と書くと、
    $$ \delta=c\cdot x=\sum_{v\in V}\lambda_v\,c\cdot v\le\sum_{v\in V}\lambda_v\delta=\delta $$
    なので、$\lambda_v>0$ となる $v$ では $c\cdot v=\delta$、すなわち $v\in F$ である。よって $x\in\operatorname{conv}(V\cap F)$。逆に $F$ は凸集合の共通部分なので凸であり、$\operatorname{conv}(V\cap F)\subset F$ である。$F\ne\emptyset$ なら $F$ は有限集合 $V\cap F$ の凸包で凸多面体であり、その頂点は $V\cap F$ に属する(凸包 の定理「凸多面体の頂点」の 1)。逆に $v\in V\cap F$ は $P$ の端点なので、$P$ に含まれる $F$ の端点でもあり、$F$ の頂点である。面は $V$ の部分集合 $V\cap F$ で決まるので、高々 $2^{\lvert V\rvert}$ 個である。
  2. $F_i=P\cap\{c_i\cdot x=\delta_i\}$($i=1,2$)とし、$c:=c_1+c_2$、$\delta:=\delta_1+\delta_2$ とおく。$P$ 上で $c\cdot x\le\delta$ であり、等号は $c_1\cdot x=\delta_1$ かつ $c_2\cdot x=\delta_2$ のときに限る。よって $F_1\cap F_2=P\cap\{c\cdot x=\delta\}$ は面である。
  3. $F=\emptyset$ または $G=\emptyset$ なら明らかなので、どちらも空でないとする。$F=P\cap\{c\cdot x=\delta\}$、$G=F\cap\{c'\cdot x=\delta'\}$($P$ 上で $c\cdot x\le\delta$、$F$ 上で $c'\cdot x\le\delta'$)とする。$V\subset F$ なら $F=P$ で主張は明らかなので、$V\setminus F\ne\emptyset$ とし、
    $$ \eta:=\min_{v\in V\setminus F}(\delta-c\cdot v)>0 $$
    とおく。$M\ge0$ を $M\eta>\max_{v\in V\setminus F}(c'\cdot v-\delta')$ となるようにとり、$c'':=c'+Mc$、$\delta'':=\delta'+M\delta$ とおく。$v\in V\cap F$ なら $c''\cdot v=c'\cdot v+M\delta\le\delta''$ で、等号は $v\in G$ のときに限る。$v\in V\setminus F$ なら $c''\cdot v\le c'\cdot v+M(\delta-\eta)< \delta''$ である。$P$ の点は $V$ の凸結合なので $P$ 上で $c''\cdot x\le\delta''$ が成り立ち、1 の証明と同じ議論で $P\cap\{c''\cdot x=\delta''\}=\operatorname{conv}(V\cap G)$ である。一方、1 を凸多面体 $F$(頂点の全体は $V\cap F$)とその面 $G$ に使うと $G=\operatorname{conv}(V\cap F\cap G)=\operatorname{conv}(V\cap G)$ である。よって $G$ は $P$ の面である。
  4. $G=P\cap\{c\cdot x=\delta\}$($P$ 上で $c\cdot x\le\delta$)とする。$G=\emptyset$ なら $F\ne\emptyset$ なので $\dim G=-1< \dim F$ である。$G\ne\emptyset$ で $\dim G=\dim F$ とすると、$\operatorname{aff}G\subset\operatorname{aff}F$ で次元が等しいので $\operatorname{aff}G=\operatorname{aff}F$ である。アフィン関数 $c\cdot x-\delta$ は $G$ の上で $0$ なので $\operatorname{aff}G$ の上でも $0$ であり、$F\subset\operatorname{aff}F=\operatorname{aff}G$ から $F\subset P\cap\{c\cdot x=\delta\}=G$ となって $G\subsetneq F$ に反する。$\square$

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$ とする。

  1. $P^\circ=\{y\mid v\cdot y\le1\ (v\in V)\}$ は原点を内部に含む凸多面体であり、$(P^\circ)^\circ=P$ である。
  2. $F\mapsto F^\diamond$ は $\mathcal{L}(P)$ から $\mathcal{L}(P^\circ)$ への全単射で、包含を逆にする($F\subset G\iff G^\diamond\subset F^\diamond$)。逆写像は $G\mapsto G^\diamond$ である。
  3. $\emptyset^\diamond=P^\circ$、$P^\diamond=\emptyset$ であり、空でも $P$ でもない面 $F$ について $\dim F+\dim F^\diamond=n-1$ である。

原点が内部の点なので、$\varepsilon>0$ で閉球 $\{\lvert x\rvert\le\varepsilon\}$ が $P$ に含まれるものがある。

  1. $x=\sum_v\lambda_vv$(凸結合)なら $x\cdot y=\sum_v\lambda_v\,v\cdot y$ なので、$y\in P^\circ$ は「すべての $v\in V$ で $v\cdot y\le1$」と同値であり、$P^\circ$ は多面体である。$y\in P^\circ$、$y\ne0$ なら $x:=\varepsilon y/\lvert y\rvert\in P$ について $\varepsilon\lvert y\rvert=x\cdot y\le1$ なので $\lvert y\rvert\le1/\varepsilon$ であり、$P^\circ$ は有界である。有界な多面体なので凸多面体である(多面体 の定理「Minkowski–Weylの定理(凸多面体の場合)」)。$R:=\max_{v\in V}\lvert v\rvert$ は正であり($P\ne\{0\}$)、$\lvert y\rvert< 1/R$ なら $v\cdot y\le\lvert v\rvert\lvert y\rvert< 1$ なので、原点は $P^\circ$ の内部の点である。
    $P\subset(P^\circ)^\circ$ は定義から明らかである。$z\notin P$ とすると、$P$ は空でない閉凸集合なので、$a\in\mathbb{R}^n$ と $b\in\mathbb{R}$ で、すべての $x\in P$ について $a\cdot x\le b< a\cdot z$ となるものがある(凸包 の定理「点と閉凸集合の分離」の 1)。$a\ne0$ であり、$x=\varepsilon a/\lvert a\rvert\in P$ から $b\ge\varepsilon\lvert a\rvert>0$ である。$y:=a/b$ は $P$ 上で $x\cdot y\le1$ を満たすので $y\in P^\circ$ であり、$z\cdot y>1$ なので $z\notin(P^\circ)^\circ$ である。よって $(P^\circ)^\circ=P$。
  2. 段 1($F^\diamond$ は面)。$F=\emptyset$ なら $F^\diamond=P^\circ$ は面である。$F\ne\emptyset$ なら thm-cpt-faces の 1 により $F=\operatorname{conv}(V\cap F)$ なので、$y\in P^\circ$ について「すべての $x\in F$ で $x\cdot y=1$」は「すべての $v\in V\cap F$ で $v\cdot y=1$」と同値である。$P^\circ$ 上で $v\cdot y\le1$ なので、各 $P^\circ\cap\{v\cdot y=1\}$ は $P^\circ$ の面であり、その有限個の共通部分 $F^\diamond$ は thm-cpt-faces の 2 により面である。
    段 2($F^{\diamond\diamond}=F$)。$F\subset F^{\diamond\diamond}$ は定義から明らかである。$F=\emptyset$ なら、$0\in P^\circ$ と $x\cdot0=0\ne1$ から $F^{\diamond\diamond}=(P^\circ)^\diamond=\emptyset$ である。$F=P$ なら、$0\in P$ から $P^\diamond=\emptyset$ で、$\emptyset^\diamond=P$ である。$F$ が空でも $P$ でもないとき、$F=P\cap\{c\cdot x=\delta\}$($P$ 上で $c\cdot x\le\delta$)と書くと $c\ne0$ であり、$\delta$ は $c\cdot x$ の $P$ 上の最大値なので $\delta\ge c\cdot(\varepsilon c/\lvert c\rvert)=\varepsilon\lvert c\rvert>0$ である。$y_0:=c/\delta$ とおくと $y_0\in P^\circ$ で、
    $$ F=\{x\in P\mid x\cdot y_0=1\} $$
    であり、とくに $y_0\in F^\diamond$ である。$x\in F^{\diamond\diamond}$ なら $x\in P$ かつ $x\cdot y_0=1$ なので $x\in F$ である。
    段 3(全単射)。1 により $P^\circ$ も原点を内部に含む凸多面体で $(P^\circ)^\circ=P$ なので、段 1・2 を $P^\circ$ に当てはめると、$P^\circ$ の面 $G$ について $G^\diamond$ は $P$ の面で、$G^{\diamond\diamond}=G$ である。よって 2 つの写像 $F\mapsto F^\diamond$、$G\mapsto G^\diamond$ は互いに逆である。$F\subset G$ なら定義から $G^\diamond\subset F^\diamond$ であり、逆向きも同じことを $P^\circ$ の側で使えばよい。
  3. 前半は段 2 で示した。$F$ が空でも $P$ でもないとし、段 2 の $y_0$ をとる。$v\in V\setminus F$ なら $v\cdot y_0< 1$、$v\in V\cap F$ なら $v\cdot y_0=1$ である。
    $$ S:=\{y\in\mathbb{R}^n\mid v\cdot y=1\ (v\in V\cap F)\} $$
    とおくと、段 1 により $F^\diamond=P^\circ\cap S$ で、$y_0\in S$ である。$F$ のアフィン包は原点を含まない(その点はすべて $x\cdot y_0=1$ を満たす)。$\operatorname{aff}F=x_0+W$($W$ は方向の部分空間、$x_0\in F$)と書くと、$x_0\notin W$ なので $V\cap F$ の張る部分空間 $\mathbb{R}x_0+W$ の次元は $\dim F+1$ である。$S$ は斉次でない連立方程式の空でない解集合なので、$\dim S=n-(\dim F+1)$ である。$F^\diamond\subset S$ なので $\dim F^\diamond\le\dim S$。逆に、$v\in V\setminus F$ での不等式 $v\cdot y_0< 1$ は有限個なので、$y\in S$ が $y_0$ に十分近ければ $v\cdot y< 1$($v\in V\setminus F$)、$v\cdot y=1$($v\in V\cap F$)であり、$y\in P^\circ\cap S=F^\diamond$ である。よって $F^\diamond$ は $S$ の中の $y_0$ の近傍を含み、$\dim F^\diamond=\dim S=n-1-\dim F$ である。$\square$

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^\diamond$ の計算を開く

$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)
表の確かめ

どの行も、表の左の条件だけを外している。

4 行の確かめを開く

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方程式 の記事は、単純な凸多面体の面の数の関係式を、極双対を通して単体的な側から見る注意を述べている。

関連項目

参考文献

[1]
Matthias Beck, Sinai Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, 2nd ed., Undergraduate Texts in Mathematics, Springer, 2015, §2.1(凸多面体・次元・支持超平面・面・ファセット・辺・頂点の定義)、Exercise 2.5(面の面は面)、Exercise 2.6(単体の面)、第 4 章の注 5(極双対の定義)、§5.1(面束の定義)、Exercise 5.9 (a)・(b)(極双対と面束の逆転、単純と単体的)。頁は著者公開の電子版(2020-06-19)で pp. 27–28、53–54、97、102、110

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