グラフ描画

平面は $(a,b,c)\neq(0,0,0)$ によって $\{(x,y,z)\mid ax+by+cz=e\}$ と書ける。$\gamma(t)$ がこの平面にあることは $ct^3+bt^2+at-e=0$ と同値である。左辺は $0$ でない（$a,b,c$ のどれかが $0$ でない）次数 $3$ 以下の多項式なので、根は高々 3 個である。よって 4 点を含む平面はない。3 点が 1 直線上にあれば、その直線と第 4 の点 $\gamma(t_4)$（$t_4$ は $t_1,t_2,t_3$ と異なる任意の値）を含む平面が 4 点を含むので矛盾する。$\square$

頂点の点は相異なる。lem-gd-moment により 3 つの頂点の点は 1 直線上にないので、どの辺の線分の内部にも頂点の点はない。2 本の辺の線分 $\sigma,\sigma'$ が内点を共有したとする。両端が 4 つとも相異なれば、2 つの線分は交わるので同じ平面にあり、4 つの頂点の点が 1 つの平面に含まれて lem-gd-moment に反する。共通の端点 $\gamma(t_i)$ をもつ場合、他方の端を $\gamma(t_j),\gamma(t_k)$（$j\neq k$）とすると、2 つの線分は $\gamma(t_i)$ のほかにもう 1 点を共有するので、同じ直線の上にあり、3 点 $\gamma(t_i),\gamma(t_j),\gamma(t_k)$ が 1 直線上にあることになって矛盾する。$\square$

段 1（方向の選択）．$\det(Q_2-Q_1,d)>0$ かつ $\det(Q_1-Q_k,d)>0$ をみたすベクトル $d$ をとる。2 つの条件はそれぞれ原点を通る直線の片側の開半平面を表す。2 つの半平面が交わらないのは、2 つの直線が一致して向きが逆、すなわち $Q_k-Q_1$ が $Q_2-Q_1$ の正の数倍のときに限るが、そのとき辺 $Q_1Q_2$ と $Q_kQ_1$ が重なって多角形が単純でなくなる。よって $d$ はとれる。
段 2（すべての辺の左側にあること）．$\varepsilon>0$ とし $x:=Q_1+\varepsilon d$ とおく。
$$ \det(Q_1-x,Q_2-x)=\varepsilon\det(Q_2-Q_1,d)>0,\qquad \det(Q_k-x,Q_1-x)=\varepsilon\det(Q_1-Q_k,d)>0 $$
である。$2\le j\le k-1$ については、$x=Q_1$ で $\det(Q_j-Q_1,Q_{j+1}-Q_1)>0$ なので、連続性により $\varepsilon$ が十分小さければ $\det(Q_j-x,Q_{j+1}-x)>0$ である。こうして、$j=1,\dots,k$ のすべてで $\det(Q_j-x,Q_{j+1}-x)>0$ となる $x$ が得られた。
段 3（扇形に分かれること）．$Q_j-x$ から $Q_{j+1}-x$ へ反時計回りに測った角を $\theta_j$ とすると、段 2 により $0< \theta_j< \pi$ である。$\theta_1+\dots+\theta_k$ は折れ線が $x$ のまわりを回る回数（回転数）の $2\pi$ 倍である。単純な多角形の回転数は、内部の点で $\pm1$、外部の点で $0$ である（回転数 の注意「単純閉曲線の回転数」。この記事では証明しない）。和は正なので回転数は $1$、すなわち $x$ は内部にあって $\theta_1+\dots+\theta_k=2\pi$ である。したがって $x$ から $Q_1,\dots,Q_k$ へ向かう半直線は、反時計回りにちょうど 1 周する順に並び、三角形 $xQ_jQ_{j+1}$ は隣り合う半直線の間の角領域に 1 つずつ入る。よってそれらの内部は互いに交わらず、和は境界が多角形 $Q_1\cdots Q_k$ の閉領域、すなわち多角形の閉領域である。開線分 $(x,Q_j)$ は隣り合う 2 つの三角形の共通の辺の内部なので、多角形の内部に含まれる。$\square$

lem-gd-reduction により、平面三角形分割 $G$ について、面の構造が同じ直線の平面描画があることを頂点数 $n$ の帰納法で示せばよい（$n\le2$ のグラフは明らかに直線で描ける）。$n=3$ なら $G$ は三角形で、三角形の頂点に置けばよい。$n\ge4$ とする。外面の境界は 3 頂点なので、外面の境界にない頂点 $P$ がある。lem-gd-link の閉路 $C_P=P_1\cdots P_k$ をとる。$P$ と $P$ に接続する辺を除くと、$C_P$ の内側は 1 つの面になる。そこに $P_1$ と $P_3,\dots,P_{k-1}$ を結ぶ互いに交わらない弧を描き足したもの（例えば、もとの辺 $P_1P$ と $PP_j$ をつないだ弧を $P$ の近くで少しずらす）を $G^\ast$ とする。
場合 1：$G^\ast$ が単純グラフのとき．$G^\ast$ は $n-1$ 頂点の平面三角形分割で、その面は、$G$ の面のうち $P$ に接しないものと、三角形 $P_1P_jP_{j+1}$（$2\le j\le k-1$）である。帰納法の仮定により、$G^\ast$ と面の構造が同じ直線の平面描画がある。その中で、三角形 $P_1P_jP_{j+1}$ は内部に何もない退化しない三角形として描かれ、隣り合う 2 つは共通の辺 $P_1P_{j+1}$ の反対側にあるので、$\det(P_j-P_1,P_{j+1}-P_1)$ の符号はすべて等しい。必要なら番号を逆順に付け替えて（または全体を鏡映して）正とする。これらの三角形と弦を合わせたものは、$C_P$ の描く多角形の閉領域である。lem-gd-kernel の点 $x$ をとり、弦 $P_1P_3,\dots,P_1P_{k-1}$ を除いて、$P$ を $x$ に置き、線分 $xP_1,\dots,xP_k$ を描く。lem-gd-kernel により、これらの線分はほかと交わらず、新しい面は三角形 $xP_jP_{j+1}$ である。ほかの面は変わらないので、$G$ と面の構造が同じ直線の平面描画が得られる。
場合 2：$G^\ast$ が単純グラフでないとき．ある弦 $P_1P_j$（$3\le j\le k-1$）が $G$ の辺としてすでにある。その辺は $C_P$ の外側を通るので、長さ $3$ の閉路 $A=P_1PP_jP_1$ は $P_2$ と $P_k$ を内側と外側に分ける（Fár48 Lemma 5、p. 232）。$A$ とその外側の部分からなるグラフを $G_1$、$A$ とその内側の部分からなるグラフを $G_2$ とすると、どちらも平面三角形分割で、頂点は $G$ より少ない。帰納法の仮定により、$G_1$、$G_2$ と面の構造が同じ直線の平面描画 $\hat G_1$、$\hat G_2$ がある。$\hat G_1$ では $A$ は内部に何もない三角形 $\Delta_1$ であり、$\hat G_2$ では $A$ は外面の境界の三角形 $\Delta_2$ で、$\hat G_2$ 全体は $\Delta_2$ の閉領域に含まれる。$\Delta_2$ の頂点を $\Delta_1$ の対応する頂点に写すアフィン変換 $\varphi$ は、線分を線分に、$\Delta_2$ の閉領域を $\Delta_1$ の閉領域に写す。$\hat G_1$ と $\varphi(\hat G_2)$ を合わせると、$G$ と面の構造が同じ直線の平面描画になる。$\square$