Implementation of a sweep line algorithm for the straight line segment intersection problem

We describe a robust and efficient implementation of the Bentley-Ottmann sweep line algorithm [1] based on the LEDA library of efficient data types and algorithms [7]. The program eomputes the planar graph G indueed by a set S of straight line segments in the plane. The nodes of G are all endpoints and all proper interseetion 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 direeted from left to right or upwards. The algorithm runs in time O«n + s) logn) where n is the number of segments and s is the number of vertices of the graph G. The implementation uses exaet arithmetic for the reliable realization of the geometrie primitives and it uses floating point filters to reduee the overhead of exact arithmetic