1

2-D 平面 (xy) に一連の点があり、n 点とします。

(x1, y1), (x2, y2), (x3, y3), ......................., (xn, yn)

私の目的はグラフを描くことです。グラフ内の 2 つのノード (点) は iff で接続され abs(difference in x coordinate) + abs(difference in y coordinate) = L(given)ます。

できますO(n*n)。効率よくできるかな。

ところで、私はこの問題を解決しようとしています

4

5 に答える 5

2

これは O( n  log  n  +  E ) 時間で実行できます。ここで、Eは最終的に得られるエッジの実際の数 (つまり、隣接ペアの数) です。

任意の点について、許可された隣接位置は辺の長さがL √2 の菱形を形成します。

        *
      *   *
    *       *
  *           *
*       o       *
  *           *
    *       *
      *   *
        *

ポイントをx  +  yでソートし、フォールバックをx  − にすると、yの場合、並べ替えられたポイントを通過する単一の O( n  +  E ) により、このタイプのすべての近傍を見つけることができます。

        *
          *
            *
              *
        o       *

ポイントごとに。(これを行うには、インデックスを使用してi近傍を見つけている現在のポイントを追跡し、別のインデックスを使用してx j  −  y j  =  x i  − jのような許可された近傍の行を追跡します。 ; y i  +  L . 配列に 2 つのインデックスがあるため、O( n 2 ) のように聞こえるかもしれませんが、トリックは で単調に増加するため、とのそれぞれが配列を1 回通過するだけです。これは次のようになります。 O( n ) パスであっても構いませんが、(jiijx i ,  y i ) の場合、それらを ( x i+1 ,  y i+1 )の潜在的な隣人として再検討する必要があるため、インクリメントすることはできませんj。したがって、O( n  +  E ) パスになります。)

次に、それらをy  − で並べ替えることができます。x  +  yにフォールバックし、プロセスを繰り返してこれらの近傍を見つけます。

        *
      *
    *
  *
*       o

また、隣人性は対称関係であるため、残りの隣人について実際に心配する必要はありません。

        o
  *           *
    *       *
      *   *
        *

(全体の O( n  log  n  +  E ) 時間には、ポイントを並べ替える O( n  log  n ) 時間と、2 つの O( n  +  E ) パスの時間が含まれます。)

于 2016-12-16T00:53:19.007 に答える