=ADD=
=reftype=
14
=number=
98-18
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1998/98-18.ps.gz
=year=
1998
=month=
11
=author=
Pau; Petru + Freiseisen; Wolfgang
=title=
A Generic Plane-Sweep for Intersecting Line Segments
=abstract=
An algorithm for reporting all intersections of
a set of line segments is presented. Based on the Bentley-Ottmann
sweep-line algorithm, it handles all degenerate cases
and takes  $O((n+n_{dip}) \log(n)+k)$ time, where
$n$ is the number of segments, $n_{dip}$ is the number of distinct
intersection points and $k$ is the size of the output.

Unlike other algorithms solving the line segment intersection
problem, we view the degenerate cases as parts of the problem.
Therefore, they are solved in the frame of a  common approach,
instead of being handled separately.
Some implementation details are also given
using the generic programming mechanism of \emph{C++}
in the frame of \cgal\ (Computational Geometry Algorithm Library).

=keywords=
computational geometry, sweep-line
=sponsor=
ESPRIT IV LTR Project No. 21957 (CGAL)