On the time complexity of line segment intersection reporting

Question

According to D. M. Mount, the optimal algorithm for line segment intersection reporting problem (monochromatic case) is O(nlogn + k) but for red-blue intersection reporting problem is O(n^4/3 log^O(1) n + k). The apparent reason behind the difference is stated as follows: The problem is considerably more difficult if monochromatic intersections exist (in the red-blue case). This is because there may be quadratically many monochromatic intersections, even if there are no bichromatic intersections.

Why can't we use the optimal line segment intersection algorithm to solve the red-blue intersection problem? That would make this problem solvable in O(nlogn + k)

Answer 1

Suppose that there are n/2 blue segments and n/2 red, that each blue segment intersects each other blue segment, and that each red segment intersects each other red segment, but that no blue and red segments intersect one another. The obvious use of the monochromatic algorithm is to generate all of the intersections and retain the red-blue ones, but this invocation has to report (n/2)(n/2-1) intersections, which makes the invoking algorithm take Omega(n^2) time even when there's nothing to report.