Reporting all intersection points, generalized segments

Description

In this case, the segments are generalized (i.e. have algebraic degree ≥1); we still wish to report all points of intersection.

Related Problems

Subproblem: Reporting all intersection points, line segments

Related: Reporting all intersection points, convex polygons, Reporting all intersection points, general polygons, Counting number of intersection points, line segments

Parameters

$n$: number of line segments

$k$: number of points of intersection

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Jean-Daniel Boissonnat and Franco P. Preparata.	1997	$O(n \log n + k \log n)$	$O(n)$	Exact	Deterministic	Time & Space
Balaban.	1995	$O(n \log n + k )$	$O(n)$	Exact	Deterministic	Time & Space
Boissonnat; Snoeyink	1999	$O(n \log n + k )$	$O(n)$	Exact	Deterministic	Time & Space

Time Complexity Graph

References/Citation

https://dl.acm.org/citation.cfm?id=304991

https://dl.acm.org/doi/10.1145/304893.304991)