いくつかの点がある平面があると想像してみましょう。与えられた半径の円もあります。
可能な最大数の点をカバーするような円の位置を決定するアルゴリズムが必要です。もちろん、そのような位置はたくさんあるので、アルゴリズムはそのうちの1つを返す必要があります。
精度は重要ではなく、アルゴリズムは小さな間違いをする可能性があります。
写真の例を次に示します。
入力：
int n（n <= 50）–ポイント数;
float x[n]およびfloat y[n]–ポイントのX座標とY座標を持つ配列。
float r–円の半径。
出力：
float cxおよびfloat cy–円の中心の座標
アルゴリズムの電光石火の速度は必須ではありませんが、遅すぎてはいけません（この状況に対するいくつかの遅い解決策を知っているため）。
C ++コードが推奨されますが、必須ではありません。
提案されているように、より良い表現に編集されました：
基本的な観察：
その場合、アルゴリズムは次のようになります。
これは、文献の「ディスク部分カバーの問題」であり、グーグルを開始するのに適した場所になるはずです。これが1つの可能な解決策をカバーする論文ですが、数学的には少し強烈です： ディスク部分カバー問題の近似アルゴリズム設計
実際のところ、これは計算幾何学と呼ばれる領域に該当します。これは魅力的ですが、理解するのが難しい場合があります。この主題に関連するさまざまなアルゴリズムについて、deBergによる優れた概要があります。
単純なものが必要な場合は、ランダムな位置（x、y）を取り、円の内側の点の数を計算して、前の位置と比較します。最大を取る。いつでも操作を繰り返します。
なぜ地獄の反対票？モンテカルロ法について聞いたことがありますか？実際には、膨大な量のポイントについて、決定論的アルゴリズムが妥当な時間内に終了しない場合があります。
ここに2つのアイデアがあります：O（n）近似アルゴリズムとO（n ^ 2 log n）正確な（非近似）アルゴリズム：
高速近似
局所性鋭敏型ハッシュを使用します。基本的に、各ポイントを、近くのすべてのポイントを含むハッシュバケットにハッシュします。バケットは、衝突が近くのポイント間でのみ発生するように設定されています。同様の名前のハッシュテーブルとは異なり、ここでは衝突が役立ちます。バケット内の衝突の数の実行カウントを保持し、次にそのバケットの中心を円の中心として使用します。
これは、最初に聞いたときにあまり明白ではない概念の簡単な説明であることを認めます。例えは、多くの人々に彼らの郵便番号が何であるかを尋ね、最も一般的な郵便番号を使用して最も人口の多い円を決定することです。完璧ではありませんが、高速なヒューリスティックです。
これは基本的にポイント数の点で線形時間であり、データセットをその場で更新して、ポイントごとに一定の時間で新しい回答を段階的に取得できます（n =ポイント数に関して一定）。
一般的な局所性鋭敏型ハッシュについて、またはこの場合に機能する私の個人的なお気に入りのバージョンについての詳細。
ブルートフォースよりも優れた決定論的アプローチ
アイデアは次のとおりです。各ポイントについて、そのポイントに円のエッジを配置し、円をスイープして、どの方向に最も多くのポイントが含まれているかを確認します。すべてのポイントに対してこれを行うと、グローバル最大値が見つかります。
点pの周りのスイープは、次の方法でn log n時間で実行できます。（a）円を角度シータに配置したときにqが含まれるように、他の点qごとの角度間隔を見つける。（b）線形時間でpの周りを行進/スイープできるように、間隔を並べ替えます。
したがって、固定点pに接触する最適な円を見つけるにはO（n log n）の時間がかかり、次にそれをO（n）で乗算して、すべての点のチェックを実行します。合計時間はO（n ^ 2 log n）です。
問題は、関数fのグローバル最適値を見つけることに戻ります。fの入力は円の中心点であり、値はもちろん、セットに含まれる点の数です。関数のグラフは不連続で、階段のようになります。 :R x R -> N
セット内のポイントに対応する各ポイントで関数をテストすることから始め、fの値を減らしてポイントを並べ替え、次にそれらのポイントの周りの検索を強化します（たとえば、らせんに沿って移動します）。
別のオプションは、セット内のポイントの任意のペアを接続するセグメントのすべての交点を考慮することです。あなたの最適なポイントは、私が思うにこれらの交差点の1つになりますが、それらの数はおそらく考慮するには大きすぎます。
オプション1と2をハイブリッド化して、「適切な設定点」の周囲の点から生成されたセグメントの交差を検討することもできます。
とにかく、設定点の数が少ない（すべての交差点をチェックできる）場合を除いて、最適なものを見つけることを保証できるとは思いません（ちょうど良い解決策です）。
一見すると、四分木ソリューションと言えます。
また、与えられたデータのクラスターを作成するK-meansと呼ばれる情報の視覚化/データマイニング方法があります。それはあなたの目的に合うように最終的に追加された機能で使用することができます。
K-Meansの基本的なアルゴリズムは次のとおりです。
追加された機能は次のようになります。
出典：
K-meansアルゴリズム-LinköpingUniversityQuadtree
- en.wikipedia.org /wiki/Quadtree
ウィキペディアをすばやく検索すると、ソースコードが見つかります：en.wikipedia.org/wiki/K-means_clustering
精度が重要ではなく、アルゴリズムが小さな間違いをする可能性があるというのが本当なら、私は次のように思います。
Letf(x,y)は、点（0,0）で最大値を持ち、半径Rの円の内側の点でのみ有意である関数です。たとえば、f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}。
ポイント(x_i,y_i)とE_i(x,y) = f(x - x_i, y - y_i)。
あなたの問題は、の最大値を見つけることです\sum_i E_i(x,y) 。
各ポイントから開始する最急降下法を使用できます。
密度マップを提案してもいいですか？xとyの最小境界と最大境界を見つけます。x境界とy境界の範囲を、円の直径に等しい幅のビンに分割します。xとyの各ビンのポイント数を別々に数えます。次に、密度マップ上で、最高ランクのxビンと最高ランクのyビンの間の交点を見つけます。
これは、大きなデータセットをすばやく一般化するための非常に高速なアルゴリズムですが、常に正確であるとは限りません。精度を向上させるために、ビンを細かく分割したり、ビンの位置を左または右にn回シフトしたりして、投票システムを使用して試行の間に最も頻繁に発生する答えを選択してください。
領域全体をピクセル化してから、各ポイントに移動し、そのポイントの周囲の半径の円内のすべてのピクセルの値を増やすことができます。合計が最も高いピクセルが適切な候補です。
もちろん、丸め誤差が原因で、一部の適切な領域が失われたり、適切な領域が「半減」したりする場合があります。おそらく、最初に大まかなピクセル化を試みてから、有望な領域を改良することができます。
これは有名なK最接近点アルゴリズムです。ここで説明：http ：//www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf