MPI-INF/SWS Research Reports 1991-2021

# MPI-I-94-160

## Implementation of a sweep line algorithm for the Straight \& Line Segment Intersection Problem

### Mehlhorn, Kurt and Näher, Stefan

#### October 1994, 41 pages.

.
##### Status: available - back from printing

We describe a robust and efficient implementation of the Bentley-Ottmann sweep line algorithm based on the LEDA library of efficient data types and algorithms. The program computes the planar graph \$G\$ induced by a set \$S\$ of straight line segments in the plane. The nodes of \$G\$ are all endpoints and all proper intersection points of segments in \$S\$. The edges of \$G\$ are the maximal relatively open subsegments of segments in \$S\$ that contain no node of \$G\$. All edges are directed from left to right or upwards. The algorithm runs in time \$O((n+s) log n)\$ where \$n\$ is the number of segments and \$s\$ is the number of vertices of the graph \$G\$. The implementation uses exact arithmetic for the reliable realization of the geometric primitives and it uses floating point filters to reduce the overhead of exact arithmetic.

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-160

BibTeX
@TECHREPORT{MehlhornNaeher94,
AUTHOR = {Mehlhorn, Kurt and N{\"a}her, Stefan},
TITLE = {Implementation of a sweep line algorithm for the Straight \& Line Segment Intersection Problem},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-94-160},
MONTH = {October},
YEAR = {1994},
ISSN = {0946-011X},
}