View source for Reporting all intersection points, line segments

{{DISPLAYTITLE:Reporting all intersection points, line segments (Line segment intersection)}}
== Description == 

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.

== Related Problems == 

Generalizations: [[Reporting all intersection points, generalized segments]]

Subproblem: [[Counting number of intersection points, line segments]]

Related: [[Reporting all intersection points, convex polygons]], [[Reporting all intersection points, general polygons]]

== Parameters == 

n: number of line segments

k: number of points of intersection

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Naive (Reporting all intersection points, line segments Line segment intersection)|Naive]] || 1940 || $O(n^{2})$ || $O(n+k)$ total ($O({1})$ auxiliary if excluding input and output) || Exact || Deterministic ||  
|-
| [[Bentley–Ottmann algorithm (Reporting all intersection points, line segments Line segment intersection)|Bentley–Ottmann algorithm]] || 1979 || $O( n log n + k log n)$ || $O(n)$ auxiliary || Exact || Deterministic || [https://doi-org.ezproxy.canberra.edu.au/10.1109%2FTC.1979.1675432 Time] & [https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/147508.147511 Space]
|-
| [[Chazelle & Edelsbrunner (Reporting all intersection points, line segments Line segment intersection)|Chazelle & Edelsbrunner]] || 1992 || $O( nlog n + k )$ || $O(n+k)$ total? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/147508.147511 Time & Space]
|-
| [[CHAZELLE (Reporting all intersection points, line segments Line segment intersection)|CHAZELLE]] || 1986 || $O( n*log^{2}(n)/(log log n) + k)$ || $O(n+k)$ total (and possibly auxiliary as well?) || Exact || Deterministic || [https://www-sciencedirect-com.ezproxy.canberra.edu.au/science/article/pii/0022000086900255 Time & Space]
|-
| [[Goodrich (Reporting all intersection points, line segments Line segment intersection)|Goodrich]] || 1989 || $O(log^{2}(n))$ || $O(n+k)$ total? || Exact || Parallel || [https://dl-acm-org.ezproxy.canberra.edu.au/citation.cfm?id=72950 Time]
|-
|}

== Time Complexity graph == 

[[File:Line segment intersection - Reporting all intersection points, line segments - Time.png|1000px]]

== Space Complexity graph == 

[[File:Line segment intersection - Reporting all intersection points, line segments - Space.png|1000px]]

== Pareto Decades graph == 

[[File:Line segment intersection - Reporting all intersection points, line segments - Pareto Frontier.png|1000px]]

== References/Citation == 

https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/147508.147511 

https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1145/304893.304991)