Reporting and Counting Intersections Between Two Sets of Line Segments

This work considers the problem of computing all intersections between two sets S and T of line segments in the plane, where no two segments in S (similarly, T) intersect and presents an asymptotically optimal algorithm which reports all those intersections in O(n log n + k) time and O( n) space.

Abstract

We consider the problem of computing all intersections between two sets S and T of line segments in the plane, where no two segments in S (similarly, T) intersect. We present an asymptotically optimal algorithm which reports all those intersections in O(n log n + k) time and O(n) space, where n is the total number of line segments, and k is the number of intersections. Our algorithm works also for general arcs of single-valued curves, within the same time bounds. Applications include the intersection of two polygons and the "merge" of two planar maps in time O(n log n + m) and space O(n + m), where n and m are the number of input and output edges, respectively. In the case of straight line segments, a simple modification allows us to count the number of intersections (without reporting them) in time O((n +√ nk)log n) = O(n 1.5log n).