Computational Geometry

Department of Computer Science

Topological sweep of the Complete Graph

Reporting all intersections of line segments and their characteristics is one of the early and most fundamental problems in computational geometry.
We concentrate on the problem of A graph presents some difficulties for a sweep line algorithm that most of the existing sweep based algorithms do not handle.
We present a novel approach that sweeps a complete graph of N vertices and
k intersection points in optimal O(k)=O(N^4) time and O(N^2) space, that is simple and easy to code and resolves the difficulties in the graph sweep.
The algorithm sweeps the graph using a topological line, borrowing the concept of horizon trees from the topological sweep method [4]
and using ideas from [3] to deal with degeneracies.
The novelty in our approach is the use of the **moving wall** that separates at any time the graph into two regions: the region of known structure, in front of the moving wall, and the region that may contain intersections generated by edges that have not yet been registered in the sweep process, behind the wall.

Figure

A snap-shot of the sweep line in a complete graph of 6 vertices.
The green edges are the *cut* (*topological line*) edges.
The blue squares are the vertices ready to be swept (*ready
vertices) and the blue lines are the moving wall associated with the current position of the sweep line.*

Papers

[1]

"Topologically Sweeping the Complete Graph", E. Rafalin, D. SouvaineProceedings volume related to the Cologne/Twente Workshop on Graphs and Combinatorial Optimization 2005, special volume ofDiscrete Applied Mathematics, submitted for publication, October 2005.[2]

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

"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[4]

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

"Algorithms for bivariate medians and a Fermat-Torricelli problem for lines",G. Aloupis, S. Langerman, M. Soss, and G. Toussaint.Comp. Geom. Theory and Appl. 26(1):69--79, 2003

Code

A README file describing how to use the code.

A tar.zip version of the code.

Related sites

Topologically Sweeping in degenerate cases

LMS regression in

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