optimization - どの円が点を囲んでいるかを確認するための効率的な構造を探しています

Question

特定の半径を持つランダムな場所にそれぞれ重なり合う円の大規模なセットがあります。

type Circle =
    struct 
      val x: float
      val y: float
      val radius: float
    end

タイプの新しいポイントが与えられた

type Point =
    struct
      val x: float
      val y: float
    end

セット内のどの円が新しい点を囲んでいるか知りたいです。線形検索は自明です。円を保持し、提示されたポイントに対して O(N) よりも優れた囲み円を返すことができる構造を探しています。

理想的には、構造は新しい円の挿入と円の削除に対しても高速である必要があります。

これを F# で実装したいのですが、どの言語で考えても問題ありません。

ご参考までに、実装を検討しています

しかし、新しい点ごとにすべての円をスキャンする単純なアプローチを使用すると、O(N^2) になります。

score 2 · Accepted Answer

Quadtree は効率的な平面検索のための構造です。平面のサブディビジョンを保持するために使用できます。

たとえば、次のようなプロパティを使用して四分木を作成できます。2. すべてのセルに含まれる円は K 個以下 (たとえば 10 個) // 壊れている可能性がある 3. ツリーの高さは M (通常 O(log n)) によって制限される

重なり合ったセルを反復することにより、四分木を構築できます。セル内の円の数が K を超える場合は、そのセルを 4 つに分割します (最大高さを超えない場合)。また、円内のセルの場合、その細分化は無意味であるため、何かを考慮する必要があります。

円を見つけるときは、クワッドツリーをローカライズしてから、重なり合う円を反復処理して、点を含む円を見つける必要があります。

まばらな円分布の場合、検索は非常に効率的です。

私は学士論文を持っており、最も近いセグメントの場所に四分木を適応させ、予想される時間は O(log n) でした。ここでも同様のアプローチを使用できると思います。

3 に答える 3