22

雲の中の3点の最も近いグループを見つけるための既知の効率的なアルゴリズムはありますか?

これは、最も近い点のペアの問題に似ていますが、2 点ではなく 3 点を探しています。

編集
「最も近い」の定義は、アルゴリズムの複雑さに影響します。ジャックが指摘したように、三角形の最小面積を見つけることは3和が難しく、いずれにしても私のアプリケーションにはあまり適していません。

最小境界線(つまり |AB|+|AC|+|BC|) 三角形または同様のもの (最小 |AB|²+|AC|²+|BC|² など)を見つけるためのより効率的なアルゴリズムがあることを願っています。 ) 他の場所に 3 つの同一線上の点が存在しても結果に影響しないため、これを 3 サム ハードにする理由はわかりません。

注: 私のポイントは 8 次元であるため、より少ない次元に制限されているアルゴリズムは適切ではありません。

4

4 に答える 4

7

この問題は、一連のポイントで最も近いペアを見つけるという古典的な問題に似ています。最も近いペアの問題を解決する最悪のケースのO(n log n)アルゴリズムを適応させて、この問題を解決できます。

特定の問題は、Google の Code Jam コンテストで取り上げられました。分析の履歴書は次のとおりです。

ポイントの数は非常に多くなる可能性があるため、効率的なアルゴリズムが必要です。分割統治法を使用すると、 O(n log n)時間で問題を解決できます。ポイントのセットを垂直線で同じサイズの 2 つのセットに分割します。最小周囲三角形には 3 つのケースがあります。その 3 つの点は完全に左側のセットにあるか、完全に右側のセットにあるか、または各半分のポイントを使用することができます。

さらに遠く：

「3 番目のケースの最小周長を見つけるには (p より小さい場合)」:

  1. 垂直分離線から p/2 の距離内にあるポイントを選択します。
  2. 次に、これらのポイントを上から下に繰り返し処理し、サイズが pxp/2 のボックス内のすべてのポイントのリストを維持します。ボックスの下端は、最後に考慮されたポイントです。
  3. ボックスに各ポイントを追加すると、そのポイントとボックス内の各ポイントのペアを使用して、すべての三角形の周長が計算されます。(分割線の左側または右側にある三角形は、既に考慮されているため、完全に除外できます。)

箱の中の点の数は最大で 16 であることを証明できるので、各点について最大で一定数の三角形を考慮する必要があるだけです。

|AB|²+|AC|²+|BC|² の場合でも動作するようにメソッドを適応させることもできるようです。

于 2011-09-30T09:28:53.960 に答える
5

で動作する明白なアルゴリズムがありますO(n^2)。

1) Delaunay 三角形分割-O(n log n)を実行すると、平面グラフが得られます。

最小角度を最大化するのは Delaunay 三角形であるため、最も近い 3 点が少なくとも 2 つのエッジで接続されている必要があることは明らかです (ただし、必ずしも三角形を形成する必要はありません!)。そうしないと、より近いポイントまたはより多くの閉じた角度が存在することになります。

2) 各ポイント (グラフの頂点) について、隣接するエッジの各ペアを調べ、これらの 2 つのエッジによって定義される 3 つの頂点を調べます。

ステップ 2) にはどのくらいの時間がかかりますか? グラフは平面であるため、エッジの数は <= 3n - 6、つまりO(n)です。したがって、この手順はO(n^2)最悪の場合 (O(n)各頂点の次数が制限されている典型的なケース) で行われます。

したがって、アルゴリズム全体はO(n^2). ステップ 2) は何らかの形でナイーブ (ブルート フォース) ソリューションであることに注意してください。そのため、改善の余地があると思います (また、ステップ 1 と 2 はおそらく何らかの形でマージされる可能性があります)。

于 2011-09-30T14:51:17.550 に答える
1

あなたが言及した問題は、3sum hard problem のバリエーションです。詳細については、http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdfをご覧ください。

この問題は、与えられた点から最小の三角形を見つけることとして表現することもできます。

編集：

基本的に、3sum hard problem は下限が O(n^2) であることを意味します。あちこちで小さな改善が見られるかもしれませんが、大したことはできません。

この特定の問題 (最小の三角形) については、http://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdfの第 3 章を参照してください。

于 2011-09-24T16:13:54.493 に答える
1

これは、 k 最近傍問題の特定の形式、つまり k=3 の場合です。引用されたページはアルゴリズムの複雑さを指定していませんが、選択したポイントから他のすべてのポイントまでの距離を計算し、そのポイントから他のすべてのポイントまでの距離を計算する単純なアプローチであることは明らかです。新しく選択したポイントへの元のポイントは O(n k-1 ) です。疑似コードを考えてみましょう:

for pointB in searchSpace do:
    distanceAB := calculateDistance(pointA, pointB)
    for pointC in {searchSpace} - {pointB} do:
        distanceBC := calculateDistance(pointB, pointC)
        distanceCA := calculateDistance(pointC, pointA)
        if (distanceAB + distanceBC + distanceCA) < currentMin then:
            currentMin := distanceAB + distanceBC + distanceCA
            closestPoints := {pointA, pointB, pointC}

pointAは からすでに削除されていると想定していることに注意してくださいsearchSpace。これは O(n 2 ) アルゴリズムです。次元が比較的小さい、または関数calculateDistanceが次元と共に線形またはそれ以下に成長すると仮定すると、適切な時間制約で解が得られます。最適化は確かに行うことができますが、必要ではない場合があります。

実際のコードを見たい場合は、ウィキペディアに実装へのリンクがたくさん あります。

于 2011-09-29T18:55:29.113 に答える