4

次の問題を最適な方法で解決する必要があります。

入力データは次のとおりです。

  • 整数座標の (x, y) ペアとして与えられる平面上の N 点
  • 円の中心を表す整数座標の (x, y) ペアとして与えられる同じ平面上の M 点。このすべての円の端には (0, 0) があります。

選択した円または選択した円の端に最初の N 点からの点がない「良い」円よりもプロパティを持ついくつかの円を分離する方法を見つける必要があります。

点と円の数は 100,000 のオーダーです。すべての点ですべての円をチェックする明白な解決策は、複雑さ O(N * M) を持ち、100,000 の円と 100,000 の点で、64 ビット SSE3 単精度コードを使用する Core 2 Duo で約 15 秒かかります。私が競合する参照実装は、同じデータで約 0.1 秒しかかかりません。リファレンス実装が O(Nlog N + Mlog M) であることは知っています。

次の方法でアルゴリズムを最適化することを考えました。ポイント データの 2 つのコピーを作成し、それぞれ x 座標、y 座標に関してコピーを並べ替えます。次に、[(xc - r, yc - r); で定義される正方形内にある点のみを使用します。(xc + r, yc + r)]、ここで (xc, yc) は半径 r の「現在の」円の中心です。ソートされたデータを扱うようになったので、バイナリ検索を使用してその間隔内のポイントを見つけることができます。このアプローチの複雑さは O(Nlog N + Mlog^2 N) である必要があり、実際には参照よりも高速ですが、それでもかなり低速です。

リファレンス実装がどのように機能するかはある程度知っていますが、理解できない手順がいくつかあります。私がこれまでに知っていることを説明しようとします：

座標 (Xc, Yc) の円の半径は次のとおりです。

  • Rc = sqrt(Xc * Xc + Yc * Yc) (1)

これは、(0, 0) が円の端にあるためです。

点 P(x, y) が円の外側にあるためには、次の不等式が真でなければなりません。

  • sqrt((Xc - x)^2 + (Yc - y)^2) > Rc (2)

ここで、Rc を (1) から (2) に代入すると、いくつかの簡単な計算を行った後に不等式を 2 乗すると、次のようになります。

  • Yc < 1/2y * (x^2 + y^2) - Xc * x/y (3.1) for y > 0
  • Yc > 1/2y * (x^2 + y^2) - Xc * x/y (3.2) for y < 0

(3.1) と (3.2) は、入力データから選択された任意の (x, y) の任意の円 C(Xc, Yc) に対して真でなければなりません。

簡単にするために、いくつかの表記を作成しましょう。

  • A(x, y) = 1/2y * (x^2 + y^2) (4.1)
  • B(x, y) = -x/y (4.2)
  • E(Xc) = 1/2y * (x^2 + y^2) - Xc * x/y = A(x, y) + Xc * B(x, y) (4.3)

与えられた円 C(Xc, Yc) に対して、(3) を次のように書けることがわかります。

  • Yc < MIN(E(Xc)) (5.1) y > 0 のすべてのポイント
  • Yc > MAX(E(Xc)) (5.2) y < 0 のすべてのポイント

E(Xc) は、A(x, y) と B(x, y) の 2 つのパラメーターを持つ Xc に関する線形関数であることがわかります。つまり、基本的に E(Xc) は、ユークリッド空間で 2 つのパラメーターを持つ直線のファミリーを表します。

ここで、私が理解できない部分が来ます。彼らは、上記の段落で述べた特性により、エンベロープアルゴリズムを使用して O(N) 時間ではなく O(1) 償却時間で MIN() と MAX() を計算できると言っています。Envelope アルゴリズムがどのように機能するかはわかりません。

Envelope アルゴリズムの実装方法に関するヒントはありますか?

前もって感謝します！

編集：

問題は、数学的な意味でのエンベロープが何であるかではありません - 私はすでにそれを知っています. 問題は、O(n) よりも適切な時間でエンベロープを決定する方法です。明らかに、償却された O(1) で実行できます。

エンベロープを計算するために必要な一連の関数があり、可能なすべてのパラメーターの配列があります。最大化問題を最適な方法で解くにはどうすればよいですか?

再度、感謝します！

4

6 に答える 6

1

私は数学的なバックグラウンドを持っていませんが、この問題に 3 つのステップで取り組みます。

  • N のほとんどのポイントを破棄します。これはトリッキーな部分です。ポイントのすべてのペアは、原点から見たときにその「後ろ」の領域を「影」にします。この領域は、点から外側に向かって原点を指す 2 つのビームと、点間の円の交点によって区切られます。これの計算は、極座標でははるかに簡単かもしれません。ランダムなペアから始めて、一度に 1 つの新しいポイントを見てください。影になっている場合は、破棄します。そうでない場合は、セット内に既にあるポイントに影を落としているかどうかを確認し、エンベロープ セットのカーブを再構築します。包絡線部分を再構築するためのテストには、ほぼ一定の時間がかかります。これは、シャドウ セットが特定の小さな数を超えて成長する可能性が低いためです。これの最悪のケースは O(NlogN) のようです。

  • M のほとんどの点を破棄します。これはかなり簡単です。M からの点が、包絡集合から最も遠い点までの距離の半分よりも原点から離れている場合、その点は破棄できます。これには O(M) かかります

  • 実際のチェックで M の残りの点をフィルター処理します。これにかかる時間はNとMの分布にもよりますが、両方の数が大きくて分布が似ていれば、ほぼO(1)だと思います。

全体として、O(N log(N) + M)で可能のようです。ただし、保証はありません;）

于 2008-12-08T15:12:15.137 に答える
1

ボロノイ図でできると思います：

  • {N 点} 結合 {[0,0]} のボロノイ図を作成します
  • N 個の点に触れていない円の中心は、凸多角形である点 [0,0] のボロノイ セルの内側にある正確な円の中心です。
  • M ポイントをフィルタリングします。1 つのテストで O(log C)=O(log N) [C はセル内の頂点の数 [0,0]] を取る必要があります。

全体的な複雑さは O(N log N+M log N) である必要があります

于 2009-01-14T11:16:42.340 に答える
1

封筒に関するウィキペディアのエントリは次のとおりです。最適化におけるエンベロープ定理に関するチュートリアルです。

于 2008-12-07T20:45:36.073 に答える
1
  • 最初のセットのすべてのポイントのR ツリーを構築します。
  • 2 番目のセットの各ポイントについて、その円の境界ボックスを計算し、その境界ボックス内にある R ツリー内のすべてのポイントを検索します (返されるポイントの数に関して O(n log n))。
  • 返された各ポイントと現在検討中のポイントの間の距離を確認します。境界ボックス内にあるが円の外側にあるものはすべて破棄します。
于 2008-12-17T11:03:14.217 に答える
0

計算の他の側面を考慮してください。

たとえば、あなたは明らかに多くの距離を比較します。それぞれが SQRT を呼び出します。代わりに「距離の二乗」を比較してみませんか。SQRT はコストのかかる計算です。

于 2008-12-08T15:33:18.713 に答える
0

平方根を取ることはありません。すべての距離を二乗のままにします。そうすれば、比較もできますが、時間は 2 ～ 3 分の 1 になります。

于 2012-01-05T14:29:06.823 に答える