A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections.
Timothy M. Chan · 1994
We present a new simple algorithm for computing all intersections between two collections of disjoint line segments. The algorithm runs in O(n log n + k) time and O(n) space, where n and k are the number of segments and intersections respectively. We also show that the algorithm can be extended to handle single-valued curve segments with the same time and space bound. 1 Introduction In this paper, we consider the red/blue segment intersection problem: 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. This is a special case of the general segment intersection problem of reporting all k pairwise intersections of a given set of n line segments in the plane. Although Chazelle and Edelsbrunner[4] gave an asymptotically time-optimal algorithm for the general segment intersection problem which runs in O(n log n+k) time and uses O(n+k) space, simpler method...