Computational Geometry

Department of Computer Science

Topological Sweep in Degenerate Cases

The **Topological sweep** method of Edelsbrunner and Guibas is one
of the classical algorithms in Computational Geometry. It
sweeps an arrangement of n planar lines in *O(n ^{2})* time
and

We present an implementation of the topological sweep algorithm that handles degenerate cases such as parallel or multiple concurrent lines without requiring numerical perturbation to achieve general position. Our method maintains the time and space complexities of the original algorithm.

Let *H* be a arrangement of *n* lines in the plane.
*A Vertical line sweep* could report all intersection pairs sorted
in order of x-coordinate in *Theta(n ^{2} log n)* time and

To report all the intersection points of the lines, in quadratic time
and linear space, we use a * topological line *(cut) that sweeps
the arrangement. A topological line is a monotonic line in
y-direction, which intersects each of the *n* lines in the
arrangement exactly once. The cut is specified by the sequence of edges,
one per line, each intersected by the topological line.
A sweep is implemented by starting with the leftmost cut which includes
all semi-infinite edges ending at -infinity, and pushing it to the right
until it becomes the rightmost cut, in a series of elementary steps.
An elementary step is performed when the topological line sweeps past a
vertex of the arrangement. To keep the sweep line a topological line we
can only sweep past a vertex which is the intersection point of two
consecutive edges in the current cut (a ready vertex).

Figure

A snap-shot of the sweep line in an arrangement of 10 lines.
The green edges are the *cut* (*topological line*) edges.
The blue squares are the vertices ready to be swept (*ready
vertices)*

Papers

[1]

"Topologically Sweeping the Complete Graph in Optimal Time and Space", E. Rafalin, D. Souvaine,Tufts CS Technical Report, 2003-05[2]

"Topological Sweep in Degenerate cases", E. Rafalin, D. Souvaine, I. Streinu,Proceedings of the 4th international workshop on Algorithm Engineering and Experiments, ALENEX 02, in LNCS 2409, Springer-Verlag, Berlin, Germany, pages 155-156,Postscript version, Pdf version[3]

"Topologically Sweeping an arrangement",H.Edelsbrunner, L. Guibas,J. of Computer and System Sciences 38, 165-194, 1989[4]

"Computing Median-of-Squares Regression Lines and Guided Topological Sweep ",H.Edelsbrunner, D. SouvaineJournal of the American Statistical Association, 85, 1990, 115-119

Code

A README file describing how to use the code.

A tar.zip version of the code (including guided topological sweep).

A tar.zip version of the code that uses the CORE library for exact geometric computations (instead of epsilon arithmatic).

Related sites

Topologically Sweeping the complete graph

LMS regression in

O(ntime using guided topological sweep^{2})