1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I thought that the idea of red/blue problem is that it's easier than the monochromatic problem. So if they both have the same complexity, what is the point of having a specialized algorithm? Because it is much easier to implement? By the way, do you mean the algorithm by Balaban or some other? $\endgroup$ – zebwel Jun 3 '16 at 23:00
  • $\begingroup$ 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. $\endgroup$ – Noinia Jun 4 '16 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.