Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-379-92

Authors:

Date:

June 1992

Pages:

1

Download Formats:

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 ofO(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.