1

DM Mountによると、線分の交差レポートの問題 (単色の場合) の最適なアルゴリズムは O(nlogn + k) ですが、赤青の交差レポートの問題では O(n^4/3 log^O(1) n + k ）。違いの背後にある明らかな理由は次のように述べられています。単色の交差が存在する場合 (赤と青の場合)、問題はかなり難しくなります。これは、2 色の交点がなくても、2 次的に多くの単色の交点が存在する可能性があるためです。

赤青交差問題を解決するために、最適な線分交差アルゴリズムを使用できないのはなぜですか? これにより、この問題は O(nlogn + k) で解決可能になります

4

1 に答える 1

1

n/2 個の青のセグメントと n/2 個の赤があり、各青のセグメントが互いに交差する青のセグメントと、各赤のセグメントが互いに交差するが、青と赤のセグメントが互いに交差しないと仮定します。単色アルゴリズムの明らかな用途は、すべての交差を生成し、赤と青の交差を保持することですが、この呼び出しでは (n/2)(n/2-1) の交差を報告する必要があるため、呼び出しアルゴリズムは Omega(報告するものが何もない場合でも n^2) 時間。

于 2013-07-06T18:37:15.890 に答える