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(n2) time and O(n) space with a topological line and is a critical ingredient in several space and time efficient algorithms.
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(n2 log n) time and O(n) space. If one only needs to report the intersection points of the lines according to a partial order related to the levels in the arrangement, greater efficiency is possible.
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).
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)
[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. Souvaine Journal of the American Statistical Association, 85, 1990, 115-119
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).
Topologically Sweeping the complete graph
|
This material is based upon work supported by the National Science Foundation under grants CCF-1422311 and CCF-1423615. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. |
|