An Elementary Algorithm for Reporting Intersections of Red/Blue Curve Segments.
Jean‐Daniel Boissonnat, Antoine Vigneron · 2000
Let E r and E b be two sets of non-intersecting curve segments, let E = E r [ E b . When |E| = n, we give a new sweep-line algorithm algorithm that reports the k intersecting pairs of segments of E. Its time complexity is O((n+k) log n), it requires O(n) space and makes use of simple primitive operations.