1

根据DM Mount，线段交点报告问题（单色情况）的最佳算法是 O(nlogn + k) 但红蓝交点报告问题的最佳算法是 O(n^4/3 log^O(1) n + k ）。差异背后的明显原因如下：如果存在单色交叉点（在红蓝情况下），问题会更加困难。这是因为即使没有双色交叉点，也可能存在二次方的单色交叉点。

为什么不能用最优线段相交算法来解决红蓝相交问题？这将使这个问题在 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 回答