MathLabs

第6問

凸多角形 PP の各辺 bb に対し、bb を一辺とし PP に含まれる三角形の面積の最大値を対応させる。PP の各辺に対応させた面積の総和は、PP の面積の二倍以上であることを示せ。
ステップ 1/5: 概凸 2m2m 角形を mm 個のバタフライで被覆する
前のステップ次のステップ
ざっくり言うと

有向主対角線 PiPi+mP_iP_{i+m} が i=0i=0 から i=mi=m まで進むと向きが P0PmP_0P_m から PmP0P_mP_0 へと反転するため、多角形内部のすべての点は隣り合う二本の主対角線の間の蝶ネクタイ領域によって少なくとも一回は掃かれる。

Bi=△PiPi+1Oi∪△Pi+mPi+m+1Oi,Oi=PiPi+m∩Pi+1Pi+m+1(i=0,…,m−1)B_i=\triangle P_iP_{i+1}O_i\cup\triangle P_{i+m}P_{i+m+1}O_i,\quad O_i=P_iP_{i+m}\cap P_{i+1}P_{i+m+1}\quad(i=0,\dots,m-1)
詳しい解説

すべての内角が ≤180∘\le 180^\circ である多角形を概凸と呼ぶ（凸多角形の辺上にいくつか頂点を追加したものである）。面積 SS の概凸 2m2m 角形 QQ の頂点を P0,P1,…,P2m−1P_0,P_1,\dots,P_{2m-1}（添字は mod 2m2m）とする。i=0,…,m−1i=0,\dots,m-1 に対し、二本の主対角線 PiPi+mP_iP_{i+m} と Pi+1Pi+m+1P_{i+1}P_{i+m+1} は点 Oi∈QO_i\in Q で交わり、自己交差するバタフライ Bi=△PiPi+1Oi∪△Pi+mPi+m+1OiB_i=\triangle P_iP_{i+1}O_i\cup\triangle P_{i+m}P_{i+m+1}O_i を囲む。ii が 00 から mm まで進むと有向直線 PiPi+mP_iP_{i+m} は P0PmP_0P_m から PmP0P_mP_0 へと向きを反転させるので、任意の内部点 X∈QX\in Q はある段階 ii で直線の反対側へ移り、その BiB_i に含まれる。よって Q=⋃i=0m−1BiQ=\bigcup_{i=0}^{m-1}B_i である。