_ もっと短く書ける。
_ [証明] 背理法により、「凸多角形 Poly を含む最小の円 C1 の中心 O で凸多角形内部に無いものが存在する」と 仮定して矛盾を導く。
「凸包の分離定理」より、点 O と Poly を分離する直線が存在する。 その中で、O を通らず、Poly に接する直線 L を選ぶ。
L が円 C1 と交わる二つ点を P1, P2 とし、L と C1 で囲まれた領域のうち Poly を含む側の領域を C1' とする。 ここで、線分 P1P2 を直径とする円 C2 を描くと、これは C1' を含むが、 C2 の直径は C1 より真に小さく、C1 の最小性に反する。 (証明終)
_ この記述を読んでから、専門書とか読まずにしばらく考えていたけど、全然難しくなかった orz
_ [証明] 背理法により、「凸多角形 Poly を含む最小の円 C1 の中心 O で凸多角形内部に無いものが存在する」と 仮定して矛盾を導く。
「凸包の分離定理」より、点 O を通り、かつ Poly と交差しない直線 L が存在する （すなわち、C1 を L で切った半円 C1' は Poly を真に包含する）。 L が円 C1 と交わる二つ点 P1, P2 を結ぶ線分 P1P2 は、C1 の直径である。
ここで、 次を満たす直線 L' が存在する: O を通らず P1P2 に平行な直線 L' と C1' で囲まれた領域 C1'' が、 Poly を含みかつ L' に接する。
L' と C1' が交わる二つ点を P3, P4 とする。 Poly を含む領域 C1'' は、線分 P3P4 を直径とする円 C2 で包含できるが、 P1P2＞P3P4 なので、C1 の最小性に反する。 (証明終)
_ 「凸包の分離定理」が地味に強い。 半円程度の領域で凸多角形を包含できれば、 もっと小さい円で包含できそうなのだが、そのような円の存在は自明ではない。 離散幾何は難しいな。
リンクはご自由に。
この日記は、GNSを使用して作成されています。
2003年2月1日より 名の訪問