MathLabs
ステップ 3/6: 境界の三角形を一つずつ取り除いていく
ざっくり言うと

三角形のレンガの山の外壁から、レンガを一つずつ剥がしていくところを想像してほしい。常に露出した境界から取るので、残りの山が崩れることはない。あるレンガは外部と辺一本まるごと接し、あるレンガは角一点だけで接しているが、どちらの場合も、取り除くたびに VV、EE、FF を合わせて常に同じ決まった量だけ減らし、V−E+FV-E+F には手をつけない。

(i) one outer edge: ΔV=0, ΔE=−1, ΔF=−1;(ii) one outer vertex: ΔV=−1, ΔE=−2, ΔF=−1\text{(i) one outer edge: } \Delta V = 0,\ \Delta E = -1,\ \Delta F = -1; \qquad \text{(ii) one outer vertex: } \Delta V = -1,\ \Delta E = -2,\ \Delta F = -1
詳しい解説

外側の面から内側に向かって、三角形を一つずつ取り除いていく。外側の面にちょうど一本の辺で接している三角形は、その共有辺を消して外側の面と合体させることで取り除かれる。これにより辺が一本と面が一つ減り、VV は変わらない。外側の面にちょうど一つの頂点だけで接し、残りの二辺が境界上にある三角形は、その二辺と外側の面の反対側にある頂点を消すことで取り除かれる。これにより頂点が一つ、辺が二本、面が一つ減る。どちらの場合も V−E+FV - E + F は変わらず、この操作を続けても、より小さく、依然として連結な三角形分割グラフが残る。

このステップで使う知識