1

私は次のことを行うアルゴリズムを考え出そうとしています:

点の集合が与えられた場合、集合からの点を含まない最大の円 (クエリ点を中心とする) をクエリ点として見つけます。

これまでのところ、集合のサイト ポイントに最も近いポイントを含む領域 (セル) を見つけるためにボロノイ図を使用し、次にボロノイからのエッジ リストを使用して台形分解を構築することを考えてきました。分解から、クエリ ポイントがどのセルにあるかを見つけることができます。円の半径は、クエリ ポイントからそのセルのポイント (サイト) までの距離になります。ボロノイには O(n) ストレージが必要であり、ボロノイからの台形分解の作成も O(n) ストレージで実行できるため、このようなものを作成するために必要なストレージは線形であると思います。

*編集: クエリ時間は O(logn) でなければなりません。つまり、セットのすべてのポイントを一度に 1 つずつ反復処理することはできません。

これは正しいと思いますか、それともここで何かが欠けていますか?

また、このアルゴリズムに関して参照できる参考文献があれば教えてください。ありがとう ：）

4

2 に答える 2

3

この質問は、クエリ ポイントからセット内のそれに最も近いポイントまでの距離を求めているように見えるので、それに答える 1 つの方法は、その最も近いポイントを見つけることです。これを行う合理的な標準的な方法の 1 つは、http://en.wikipedia.org/wiki/K-d_treeを使用することです。この質問は一般的にhttp://en.wikipedia.org/wiki/Nearest_neighbour_searchで説明されています。

于 2012-06-08T04:29:14.437 に答える
0

それは非常に複雑に聞こえます。ボロニ図が何であるかさえ知りませんが、ポイントがすべて2D平面にあると仮定すると（球ではなく円に言及しているため、これは事実のようです）、これは非常に簡単です：

すべてのポイントを繰り返し処理し、クエリ ポイントに最も近いポイントを見つけます。この距離はまさにピタゴラスの定理sqrt((point_x - query_x)^2 + (point_y - query_y)^2)です。最小距離は円の半径です。

于 2012-06-08T03:05:06.817 に答える