SHORT ABSTRACT:

Given two sets S and T of line segments in the plane, where no two line segments in S (similarly, T) intersect, we would like to compute and report in an efficient manner all pairs (s,t) in SxT of intersecting line segments. We present an asymptotically optimal algorithm which reports all intersections (s,t) 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. This algorithm can be used to compute the regions of intersection of two simple polygons of O(n) edges (or, in general, to ``merge'' two straight-line embeddings of planar graphs). A simple modification allows us to count the number of intersections (without reporting them) in time O((n+ sqrt(n k))log n)= O(n**1.5 log n).

LONGER ABSTRACT:

Given two sets S and T of line segments in the plane, where no two line segments in S (similarly, T) intersect, we would like to efficiently compute and report all pairs (s,t) in SxT of intersecting line segments. This problem in computational plane geometry has obvious applications in computer aided design, particularly in the layout of integrated circuits, as well as in high-speed computer graphics. We present an algorithm which reports all intersections (s,t) 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. These bounds are optimal to within a constant factor.

This improves on the O((n+k) log n) algorithm by Bentley and Ottman, who modified an earlier ``line sweep'' algorithm due to Shamos and Hoey. More recently, B. Chazelle presented another solution running in O(n(log**2 n)/(log log n) + k ) time and O(n+k) space. Note however that both algorithms are more general than ours, since they apply to any collection of n line segments in the plane; they do not require the segments to be partitioned in two sets S and T, each of them free of intersections. Time bounds of O(n log n + k) have been mostly found in intersection problems where the inputs are rectilinearly oriented, for example the algorithm discovered by McCreight for reporting intersections of rectangles in the plane formed by vertical and horizontal line segments.

Unlike the Bentley-Ottman algorithm, ours does not report the intersections in strict left-to-right order. By a simple modification, however, it can be made to report in the correct order all intersections involving the same segment s, for every s in S or T. Thanks to this ``local order'' property, we can use our algorithm to construct the intersection of two simple polygons in O(n log n + m) time and O(n+m) space, where n and m are the number of input and output edges, respectively. The same ideas also give an optimal algorithm for merging two ``straight-line'' embeddings of planar graphs, within the same time and space bounds. This improves on a solution by Nievergelt and Preparata, who could obtain these bounds only under the assumption that the given embeddings have convex faces.

A closely related problem is that of counting the intersections, without reporting them. A simple modification to our algorithm solves this problem in O((n+ sqrt(nk)) log n)= O(n**1.5 log n) time and O(n) space. The best previous algorithm for this problem, also due to Chazelle, runs in O(n**1.695) time (but again applies to an arbitrary collection of line segments).