Median Triangulation

現在の多角形で書かれた整数が最小の頂点を $v$ とする。任意の三角形分割に対し、$v$ を端点とする対角線をすべて取り除くように対角線を変更することを考える。

1 回の変更では、頂点 $v,x,y,z$ からなる四角形の対角線 $(v,y)$ を $(x,z)$ に変更する。

$A_x\le A_z$ としてよい。このとき、変更前の $2$ つの中央値を昇順に並べると

$$\min(A_x,A_y),~\min(A_y,A_z)$$

であり、変更後は

$$A_x,~\operatorname{med}(A_x,A_y,A_z)$$

である。ただし、$\operatorname{med}$ は $3$ つの整数の中央値を表す。

$A_v$ は最小値なので、変更後の各中央値は変更前の対応する中央値以上である。したがって、全体の数列 $B$ も辞書順で小さくならない。

この変更を繰り返すことで、$v$ を端点とする対角線をすべて取り除ける。よって、$v$ と両隣の頂点からなる三角形を含む最適な三角形分割が存在する。

この三角形の中央値は固定され、残りの多角形の三角形分割は独立に選べる。したがって、残りの多角形でも同様に最小値の頂点を選べばよい。

以上より、この貪欲法で正しい解を得ることができます。