The New Jersey Line-Segment-Saw Massacre (Companion to Video)

Abstract:

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.