問題タブ [closest-points]

したがって、2 つの点 A(x1,y1) と B(x2,y2) が与えられ、x1 <= x2 かつ y1<= y2 の場合、B が A を支配していると言えます。すべての非支配点を見つけます。自明なアプローチは、すべてのポイントを他のポイントと比較し、すべての非支配ポイントを取得することです。しかし、それは O(n^2) です。だから私は分割統治を試みました。かなり簡単で、O(nlogn)でそれを見つけることができます。私たちの教授は、それはまだ O(n) で実行できると言っています。本当にありえないことだと思います。私のためにこれを解決するように頼んでいるわけではありませんが、どのような条件下でも O(n) で実行できないことを確認できる「明白な」方法があるかどうか知りたいですか? ただし、本当に可能である場合は、答えないでください。

2 つの (低次元、おそらく 2D) 単体複体 P と Q が与えられた場合、Q のある点 q に最も近い点である P のすべての点からなる P のサブセットである P' を構築するための効率的なアルゴリズムはありますか?

たとえば、P と Q が非縮退的に交差する線分である場合、P' はそれらの交点になります。それらが交差していない場合、P' はポイントまたはセグメントになります。P が線分で Q が三角形の場合、P' は P への Q の投影になります。P が三角形で、Q が P と交差する線である場合、P' は内部および/または三角形の外側。

いくつかの写真の例: (点の交差点のあるものは正しくありません)

一般に、P' は、P の (任意の次元の) 各面への Q の射影で構成されているようですが、その記述には、高次元の面によって支配されている多数の面が含まれており、どのように処理するかは私には明らかではありませんそれを効率的に。

こんにちは、このフォーラムでいくつかの調査を行いましたが、私の問題に対する適切な回答が実際には見つかりませんでした。可能な限り最速のアルゴリズムで金融問題を解決する必要があります。ポイントの p セットが与えられた場合、各セットには n ポイントがあり、すべてのポイント セット間の最も近いポイントをすべて計算するアルゴリズムを見つける必要があります。最も近いペアアルゴまたは最も近いネイバーで実行できると思いますが、o（n ^ 2）未満の操作でどのように作成できるかわかりません。

現在、グラフ全体でダイクストラのアルゴリズムを実行し、元のノードからの合計距離によってノードの最小ヒープを形成しています。次に、ヒープから上位 n 個の要素を削除します。

これは非常に非効率的だと思います。最も近い 10 個のノードを見つける必要があり、グラフに 100000 を超えるノードがあるとします。次に、グラフ全体でダイクストラを実行するのは時間の無駄のようです。しかし、問題は、グラフ内のすべてのノードへの最短パスを計算せずに、上位 10 個の最も近いノードを見つけることができる他の方法がわからないことです。

より良い方法はありますか？

ドキュメントの各ペアの値を発行するビューを作成する必要があります (_all_docs とそれ自体のデカルト積)

たとえば、DB に , , という ID を持つドキュメントがあると仮定するとa、bビューは, , , , ... のc9 つのキーを発行する必要があります(グループ化されていないと仮定します) 。aaabacbacc

たとえば、ドキュメントが座標付きの「都市」である場合、ビューは都市のペアとそれらの間の距離を返します (実際の例はより複雑です)。そのため、_list関数を使用して「最も近い都市トップ 10」などを計算できます。

これは非常に単純なタスクのように見えますが、Google および SO 検索では結果が得られません。ここに魔法のキーワードがありませんか？

次のようなファイルがあります。

そして、2 つの数値とその最も近い距離を見つけたいと思います。シェルスクリプトを使用しています。当時、私は：

次のケースでは、2 つの列を検討したいと思います。x 軸の列と y 軸の列も同様です。これは、最も近い点のペアの問題のようなものです。私もそのお手伝いがしたいです。

助けてくれてありがとう！

1 つの (x,y) 座標から 100 万の座標の配列内のすべての座標までのユークリッド距離を見つけて、距離が最も小さい座標を選択する必要があるとします。

現在、100万要素の配列をループし、距離を計算して最小値を追跡しています。別の方法でより速く行う方法はありますか。

ありがとう