問題
平面上に3つ以上の点が存在する。（ただし、全ての点が一直線に並んでいるような場合は考えない）
以下の条件を満たす三角形の集合を考える。
条件１：全ての三角形は、与えられた点のうち3つを頂点とする。
条件２：全ての点は、必ず1つ以上の三角形の頂点となる。
条件３：三角形全体の和は与えられた点の凸包に等しく、互いに辺や頂点以外では重ならない。
条件４：全ての三角形の外接円は、頂点となる3点以外の点を含まない。

条件を満たす三角形の集合は必ず存在するか？
存在する場合、それは一意な集合か？
その三角形の集合を求める具体的な手続きは存在するか？



この問題、とあるツールの一部機能として実装されていて、
つまりツールの製作者が言うには
「具体的な手続きが存在する、それに従えば三角形の集合は必ず見つかる」
ということになるんだろうなぁと。
ただその処理が入力の点の数の4乗オーダーの処理がかかっていて
結構重いんですよそのツールｗ

某所でそんな話題になったので、具体的な手続きはともかく
三角形の集合の存在について証明でも書こうかと。

途中。今は概要だけ。
補題はちょっとちゃんと証明しないといけない気がする（（２）あたり必要だったのでイメージだけで追加した

補題
平面上にABCDの4点をとるとき、以下の3つは同値。
１）△ABCの外接円（半径R_1）にDが含まれる
２）△BCDの外接円（半径R_2）にAが含まれる
３）△ABDの外接円（半径r_1）、△ACDの外接円（半径r_2）としたとき、
　　r1<R1、r1<R2、r2<R1、r2<R2


与えられた点の凸包を、条件１～３を満たすように三角形に分割する。
以下の操作を繰り返す。
A）「集合に△ABCと△BCDが存在し、△ABCの外接円にDが含まれる」ような△ABC、△BCDをとる。
B）集合から△ABCと△BCDを取り除き、かわりに△ABDと△ACDを追加する。

・Bの操作を行っても、問題の条件１～３の成立可否は変化しない。
・Bの操作を行うたびに、補題により「三角形の外接円半径の総和」は小さくなる。
・「三角形の外接円半径の総和」は三角形の集合のとりかたによって決まり、
　その集合のとりかたの総数は有限である。
　よってBの操作を無限に続けることはできず（無限降下法）、この操作は有限で停止する。
・停止するとはAの条件を満たす△ABC、△BCDを取れなくなった時であり、つまり問題の条件４を満たした時である。

NAME:

MAIL:

URL:

COLOR:
Black LimeGreen SeaGreen Teal FireBrick Tomato IndianRed BurlyWood SlateGray DarkSlateBlue LightPink DeepPink DarkOrange Gold DimGray Silver
SUBJECT:

COMMENT:

PASS: