An elementary algorithm for reporting intersections of red/blue curve segments

AbstractLet Er and Eb be two sets of x-monotone and non-intersecting curve segments, E=Er∪Eb and |E|=n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(nlogn+kloglogn) and it requires O(n) space