eomole blog » 点を円で囲む方法のあれこれMM56の問題でこんなものがありました。 平面上のすべての点をM個以下の円で覆い、それらの半径の2乗和を最小化せよ 細かい条件は省略していますが、これの厳密解を求めるのは困難ですので、 クラスタリングを行い、それぞれのクラスタについてすべてのの点を囲む最小円 (最小包含円)を求めるのがたぶん定石だと思います。 ここで問題になるのは、どうやって最小包含円を求めるかです。 そのとき調べたところいろいろあったのでまとめてみました。 計算量のところの、nは点の個数、epsは半径に対する相対誤差です。 予備知識 まず、知っておくべきことは三角形の最小包含円です。 これは、鋭角三角形と鈍角三角形で場合分けできて、円の中心は 鋭角三角形のとき、三角形の外心 鈍角三角形のとき、鈍角の対辺の中点 となります。 n^3の方法 一般の多数の点について最小包含円を求めるには、局所改善を考えると、
