ランダムな点をカバーする円の推定

Question

python 3を使用して以下の問題を解いてください、

50個の点がランダムに座標にプロットされます。
半径6の2つの円でできるだけ多く50個の点をカバーしたいと思います。多くの点をカバーできる円の中心座標を見つけてください。

この問題は難しいので、完璧な答えではなくても、ある程度の精度があれば問題ありません。

Comments

[hayataka2049]

自分でやってみて、どんなところが難しいと思いましたか？　さすがに丸投げだと回答はつきづらいです。あと、その問題の出典を示してください。そもそもこういう場で質問として公表しても構わない問題なのかどうか判断できませんし、公表に問題がなくても引用するなら出典を示すのがルールです

Answer 1

ざっくりとした質問なので、方針だけ回答します。

1.とりあえず候補となる2点が必要なので、クラスター数=2のkmeansを実行して、各クラスターの中心点を算出する。
2.上記は距離制限のない状況下のものなので、ここからx軸方向、y軸方向に少しずつ更新しながら半径に入る点の数が最大になる中心点を探索する。
3.中心点の探索はMCMCを応用する。設定した更新率に基づきx軸方向に更新した場合の点の数をカウントして改善するようなら更新する。(更新前後の点の数の比率をもとにランダムに更新するかどうかを決めたほうがいいかもしれない)
4.同じことをy軸方向について実施する。
5.項番3と4を収束するまで繰り返す。繰り返す回数は収束度合いを見ながら決める。
6.x軸、y軸の推移を取り出して値を決定する。最頻値、平均値などを使う。

クラスター分析を使うのは、ふたつの円の重なりを回避するためです。相手側の点が含まれた場合はNGにすれば少しは回避できます。
なお、他にも考慮すべき事項がありそうです。そのあたりは、コードとともに別途質問してください

Answer 2

座標系の範囲もなしだと、最悪「どの座標をとっても、半径6の円内にたかだか一つしか点が存在しない」（＝任意の2点の距離の最小が12より大きい）状態は発生しうるんですけど、その場合どうするんですかね？
しかもこのとき、「一つしか点が存在しない」座標は、大量に存在します。
なぜなら50個の点のそれぞれから半径6の円を描いたときに、それらの円はいずれも接しないし重なりもしないから、その全ての円の内側になる座標がすべて、「一つしか点が存在しない」座標になるからです