This videotape shows a line segment intersection algorithm in action and illustrates its most important features. The algorithm, due to Chazelle and Edelsbrunner [CE], has an optimal running time of O(n log n + k), where n is the number of line segments and k is the number of pairwise intersections. As in the classical Bentley-Ottmann method [BO], the algorithm operates in a sweepline fashion by scanning the segments from left to right, and maintaining the vertical visibility map of the region swept along the way. Two important differences are that (i) the schedule includes only the endpoints of the segments and not the intersection points, and (ii) the cross section along the sweepline is maintained in a lazy fashion, meaning that the nodes of the tree representing the cross section might correspond to segments stranded behind past the sweepline. Also, the loop invariant for the sweepline is not simply that the portion of the map left of it should be maintained but also that the map associated with all the segments intersecting the sweepline be available as well. Segments are cut up into smaller pieces in preprocessing, so as to enforce a normalization condition related to the schedule of insertions. Production Notes: The animation comes from a system currently being developed at Princeton by Ayellet Tal and David Dobkin. This system is intended to ease the interface between geometric code and the graphics device. It is built on top of Cheyenne, a device independent graphics library developed by David Dobkin and Eleftheros Koutsofios. The program runs on Sun and Silicon Graphics IRIS workstation. Recording was done at the Interactive Computer Graphics Lab at Princeton and editing was done with the assistance of the Princeton Department of Media Services.

J.L. Bentley and T.A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28(9):643-647, 1979.
B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM, 39(1):1-54, 1992.

This technical report has been published as

"The New Jersey Line-Segment-Saw Massacre." Ayellet Tal, Bernard Chazelle, and David P. Dobkin, Animation and geometric algorithms: A video review, ed. M. Brown and J. Hershberger, Technical Report 87b, 1993, DEC System Research Center, Palo Alto, CA.