25/05/02 09:23:00.49 Ys+Z3aDP.net
>>15
シンプルな多角形が三角形に分割できることの証明ですが、以下のような感じでどうでしょうか？
シンプルな多角形が凸な場合には、任意の頂点 i と隣接する頂点 i - 1, i + 1 の3点を頂点とする三角形は問題の多角形の部分集合です。
その三角形を取り除いた多角形もシンプルな凸多角形で頂点の数は 1 減っています。
あとは、頂点の数に関する帰納法で証明します。
凹んでいる場合ですが、凹んでいる三角形の頂点 i - 1, i, i + 1 を考えます。
頂点 i - 1 と i + 1 を結び、凹んでいる多角形の凹んでいる部分を「修復」します。
凹みがなくなるまでこの作業を繰り返します。
作業完了後、凸多角形ができあがります。
この凸多角形は三角形に分割できます。
ここからどうすればいいですかね？
「修復する」ために使用した三角形をすべて除去した後に残されたオリジナルの多角形に分割の線がひかれていますが、それは一般には三角形分割ではありません。