凸多面体

有限個の閉半空間 $\{\boldsymbol x\mid\boldsymbol n_i\cdot\boldsymbol x\le c_i\}$（$\boldsymbol n_i\ne\boldsymbol 0$、$i=1,\dots,N$）の共通部分 $P$ で、有界かつ内部が空でないものを凸多面体という。$P$ の頂点は $P$ の端点（$P$ の相異なる 2 点を結ぶ線分の、両端以外の点にならない点）、面は $P\cap\{\boldsymbol n_i\cdot\boldsymbol x=c_i\}$ のうち 2 次元のもの（一直線上にない 3 点を含むもの）、辺は相異なる 2 つの面の共通部分のうち線分（両端が異なるもの）であるものをいう。頂点・辺・面の個数を $V,E,F$ とする。凸多面体の面・辺・頂点は次の 3 つの性質をもつ（6.2 節の 定理 6.4 で証明する）。

• (P1) 各面は凸多角形で、頂点は $P$ の頂点である。1 つの頂点から引いた対角線で $n-2$ 個の三角形に分けられる（扇形分割）。
• (P2) 各面の（凸多角形としての）辺は $P$ の辺であり、各辺はちょうど 2 つの面に含まれる（したがって各辺はちょうど 2 つの面の辺になっている）。
• (P3) 相異なる 2 つの面の共通部分は、空、1 つの頂点、1 本の辺のいずれかである。