4

m「候補」と呼ばれる 2D 平面内の一連の点を想像してください。次に、次の 2 つのシナリオのいずれかを行います。

  • 点のセットn(「オブジェクト」) もあります。図 1 を参照してください。

  • nX 軸または Y 軸 (「オブジェクト」) と同一線上にある線のセットもあります。図 2 を参照してください。

すべてのペアの中でデカルト距離が最も短い候補とオブジェクトのペアを知りたいです。

この問題が計算幾何学で名前を持っているかどうか誰か知っていますか? O(m*n) よりも高速なアルゴリズムはありますか? そして、オブジェクトが同じままで、候補のみが変更される場合、巧妙な事前計算によって O(m*n) よりも高速になる可能性がありますか?

図1

              c      o
       c
                          o         c      o
           o    c
                             c
              c o              
                       c             o
                                          c
               o                 c
          c

図2

             |                      c           |  
-------------+----------------------------------+------  
             |                                  |  
             |              c                   |    c  
             c                                  |  
             |                                  |  
-------------+----------------------------------+------  
             |          c            c          |  
-------------+----------------------------------+------  
             |                            c     |
4

4 に答える 4

1

これは基本的に、すべての候補に対する最近傍検索です。kd ツリーインデックスを使用すると、この種の問題を高速化できます。

于 2013-03-27T22:15:44.140 に答える
0

オブジェクトから線を作成する方法がわかりません。オブジェクトごとに 2 本の線を作成します: 1 本は垂直方向、もう 1 つは水平方向ですよね?

いずれにせよ、垂直線 v1,v2,..,va と水平線 h1,h2,...,hb があるとします。

x 軸のオフセットに従って垂直線を並べ替え、y 軸のオフセットに従って水平線を並べ替えます。

候補セット内のすべてのポイントに対して、バイナリ検索を実行して、最も近い垂直線と水平線を取得します。最も近い (candidate,line) のペアを計算する方法は簡単です。

于 2013-03-27T22:04:04.437 に答える
0

探している名前は NNS である可能性が高く ( http://en.wikipedia.org/wiki/Nearest_neighbor_searchを参照)、「オブジェクト」の静的セットの事前計算のための時間とスペースがあれば、実行できるはずです。 O(n*m) よりも高速に検索できます。

二分探索木を構築する最も単純なアプローチを使用しても、単一のルックアップの時間の複雑さを O(log n) に削減し、問題全体の O(m log n) につながるはずです。

于 2013-03-27T22:04:23.753 に答える
0

1 つの 2d ではなく 2 つの 1d 問題があります。すべての「条件」を x 軸と y 軸に投影し、垂直の「オブジェクト」を x 軸に、水平に y に配置します。

出来上がり！2 つの 1d 問題。

今は1dです。

すべての「条件」を並べ替えられた配列に配置します。すべての「オブジェクト」について、バイナリ検索を使用して、その配列内のセグメントを含むものを見つけます (2 つの最も近い「条件」)。

結果として O(n log m + n log n)

于 2013-04-04T09:37:34.187 に答える