# Red-blue intersection requirements

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...

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.
• I guess the red/blue version is easier to think about; optimal red/blue versions are older than the optimal general version/optimal general versions. Indeed, I was referring to Balaban's algorithm. With respect to implementation; Chan's algorithm that I linked to before seems fairly easy to implement. Probably easier than the optimal version of Balaban's. He also describes a $O(n \log^2 n + k)$ time algorithm that should be ok to implement. – Noinia Jun 4 '16 at 7:19