4

数直線上の 1 点に重なる線分の数を効率的に数えることはできPますか?

すべての線分は 1 つの数直線上にあります (これは1-D世界であり、世界ではありません3-D)。

各線分には、開始座標X1と終了座標がありX2ます。

例：

Line segment A spans from X1==1 to X2==3
Line segment B spans from X1==2 to X2==4
Line segment C spans from X1==3 to X2==5
Line segment D spans from X1==1 to X2==4
----------------------------------------
Ex1: Line segments that overlap point P==2: A,B and D   >>> overlap count==3.
Ex2: Line segments that overlap point P==7: None        >>> overlap count==0.
Ex3: Line segments that overlap point P==3: A,B,C and D >>> overlap count==4.

もちろん、線分が 4 つしかない場合、コードは単純です。ただし、4 億の線分の巨大な空間データベースがある場合、検索は非常に遅くなります。

この線分のリストからオーバーラップの総数を効率的に検索できるアルゴリズムはありますか?

私がこれまでに見ているもの

4

4 に答える 4

1

単一の配列で、クエリ ポイントと間隔エンドポイントを徐々に並べ替えます。すべてのポイントについて、間隔の開始、間隔の終了、またはクエリのいずれであるかを示すフラグを保持します。

カウンターをゼロに初期化し、リストをスキャンします。開始するとカウンターが増加します。終わりはそれを減らします。クエリは、カウンターを読み取ることによって重複する間隔の数を認識します。

時間 (N+M).Log(N+M) または特別な並べ替えが使用できる場合はそれ以上。

クエリ ポイントの並べ替えが許可されていない場合は、間隔のエンドポイントを並べ替えます。1 回の線形スキャンで、各エンドポイントの直後にオーバーラップの数を計算できます。

特定のクエリ ポイントに対して、二分探索によって関連するエンドポイントを見つけるため、オーバーラップ カウントが発生します。

M 間隔と N クエリ ポイントの M.Log(M)+N.Log(M)。

間隔の並べ替えが許可されていない場合は、クエリ ポイントを並べ替えます。

すべての間隔を順番に処理し、重複する最初のクエリ ポイントを二分探索によって見つけ、重複するすべてのクエリ ポイントのカウンターを増やします。

N.Log(N)+M.Log(N)+O ここで、O は間隔/クエリのオーバーラップの総数です。

並べ替えがまったく許可されていない場合は、すべての間隔に対してすべてのクエリを徹底的にテストします.NM

于 2016-02-26T15:06:06.087 に答える
-1

まず、各線分を少なくとも 1 回は確認する必要があるため、O(N) 以上のことはできないことを理解することから始めます (ここで、N = 線分の数)。

各ポイントを通過する線分の数を格納する配列 Line_segments_at を用意しましょう。

最初に、この配列を 0 に初期化する必要があります。次に、i 番目の線分を見たときに、次のことを行う必要があります。

for(int j=x1[i];j<=x2[i];j++)
 Line_segments_at[j]++;

すべてのクエリ ポイント k について、単純に結果を Line_segments_at[k] として返すことができます。

于 2013-06-22T20:34:48.107 に答える