1

アルゴリズムからテストのために学習していますが、数日間対処できない問題を発見しました。だから私は助けを求めてここに書いています。

平面 上の与えられた2 つの互いに素な集合について:

G={(x_1^G, y_1^G), (x_2^G, y_2^G), ..., (x_n^G, y_n^G)}
D={(x_1^D, y_1^D), (x_2^D, y_2^D), ..., (x_n^D, y_n^D)}

Where for every 1 <= i, j <= n we have y_i^D < y_j^G, so G is above D.

counts the distance between them 次のように定義された効果的なアルゴリズムを見つけます 。

d(G,D) = min{ d(a,b): a \in G and b\in D }, 
where d(a,b) = |x_a - x_b| + |y_a - y_b|

O(n^2) は自明なので、答えではありません。

テスト前に復習するのは資料からなので、解決策が難しくないことを願っています。誰でも助けることができますか？

これは、よくある問題の特殊なケースのように見えると思います。しかし、それが特別な場合であれば、解決策はより簡単になるのでしょうか?

4

1 に答える 1

2

O(n log n) 時間でこれを行う方法はいくつかあります。

1: G ポイントのマンハッタン距離ボロノイ図を計算し、それに基づいてポイント位置データ構造を構築します。これには O(n log n) の時間がかかります。各 D ポイントについて、ポイント位置データ構造を使用して最も近い G ポイントを見つけます。これには、D ポイントごとに O(log n) の時間がかかります。見つけたばかりのペア間の距離の最小値を取ると、それが答えです。

2: Fortune のアルゴリズムをこの問題に適応させることができます。DポイントとGポイントのバイナリツリーを別々に保持するだけです。説明するのがちょっと面倒。

次のアイデアは、最大 (|x1-x2|, |y1-y2|) である無限ノルムの最も近いペアの距離を計算します。問題を 45 度傾けて (u = xy、v = x+y を代入)、適切な形式にすることができます。

3 (2 の変形): すべての点を y 座標で並べ替えます。これまでに確認された最も近いペア間の距離 d を維持します。G 点の 1 つと D 点の 1 つである 2 つのバイナリ検索ツリーを維持しながら、ラインを上から下にスイープします。ポイントがスイープ ラインの d 以上にある場合、そのポイントを二分探索木から削除します。スイープ ラインがポイント、たとえば D ポイントに最初に遭遇すると、(1) G 二分探索ツリーをチェックして、x 座標が新しいポイントの d 以内にある要素があるかどうかを確認し、必要に応じて d を更新します。 (2) 新しい点を D の二分探索木に挿入します。各ポイントは、一定数の二分探索木操作と一定量の追加作業のみを発生させるため、スイープは O(n log n) です。当然のことながら、並べ替えも同様であるため、全体的な時間の複雑さは希望どおりです。

3 と同様のアイデアに基づいて、分割統治戦略を機能させることもできます。

于 2012-12-08T16:19:35.250 に答える