Red-blue intersection requirements

Question

In the red-blue line segments intersection problem, what does it mean that the red-red (and blue-blue) lines cannot intersect? Does mean mean that the algorithms wont work correctly or does it mean that these kind of intersections will be simply ignored?

In other words, do the fast intersection algorithms require that the are no single-color intersections? Or they can work with such intersections but will find only bi-chromatic intersections?

The red-blue line segments intersection problem can be stated as: "Given a disjoint set of red line segments and a disjoint set of blue line segments in the plane, with a total of n segments, report all k intersections of red segments with blue segments." (From "A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections", Timothy M. Chan).

The idea, if I understood correctly, is that the problem should be easier to solve than the problem of reporting all intersections between line segments in general. So I'm trying to understand how hard the requirements are...

Answer 1

I guess it depends on the particular algorithm you have in mind. However, the red/blue segment intersection algorithms that I'm aware of require that there are no monochromatic (red/red or blue/blue) intersections. For example, Chans red/blue intersection algorithm builds a trapezoidal decomposition on the blue segments. That does not really work if there are blue/blue intersections as well.

By the way, note that both red/blue segment intersection, as well as general (monochromatic) segment intersection can be solved in optimal $O(n \log n + k)$ time.