Reporting all intersection points, line segments

The line segment intersection problem supplies a list of line segments in the Euclidean plane and asks about the points where they intersect (cross), if any. In this case, we wish to report all points of intersection.

Parameters

$n$ : number of line segments
$k$ : number of points of intersection

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Chazelle & Edelsbrunner	1992	$O(n \log n + k)$	$O(n+k)$
CHAZELLE	1986	$O(n\log^2(n)/(\log \log n) + k)$	$O(n+k)$
Bentley–Ottmann algorithm	1979	$O(n \log n + k \log n)$	$O(n)$
Naive	1940	$O(n^2)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms