Reporting all intersection points, line segments: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
 
(2 intermediate revisions by the same user not shown)
Line 14: Line 14:
== Parameters ==  
== Parameters ==  


n: number of line segments
$n$: number of line segments


k: number of points of intersection
$k$: number of points of intersection


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 26: Line 26:
|-
|-


| [[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 ||   
| [[Naive (Reporting all intersection points, line segments Line segment intersection)|Naive]] || 1940 || $O(n^{2})$ || $O({1})$ || 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/10.1109%2FTC.1979.1675432 Time] & [https://dl.acm.org/doi/pdf/10.1145/147508.147511 Space]
| [[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)$ || Exact || Deterministic || [https://doi.org/10.1109%2FTC.1979.1675432 Time] & [https://dl.acm.org/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/doi/10.1145/147508.147511 Time & Space]
| [[Chazelle & Edelsbrunner (Reporting all intersection points, line segments Line segment intersection)|Chazelle & Edelsbrunner]] || 1992 || $O( n \log n + k )$ || $O(n+k)$ total? || Exact || Deterministic || [https://dl.acm.org/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/science/article/pii/0022000086900255 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/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/citation.cfm?id=72950 Time]
| [[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/citation.cfm?id=72950 Time]
|-
|-
|}
|}
Line 41: Line 41:


[[File:Line segment intersection - Reporting all intersection points, line segments - Time.png|1000px]]
[[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]]
== Space-Time Tradeoff Improvements ==
[[File:Line segment intersection - Reporting all intersection points, line segments - Pareto Frontier.png|1000px]]


== References/Citation ==  
== References/Citation ==  

Latest revision as of 09:05, 28 April 2023

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

Name Year Time Space Approximation Factor Model Reference
Naive 1940 $O(n^{2})$ $O({1})$ Exact Deterministic
Bentley–Ottmann algorithm 1979 $O( n \log n + k \log n)$ $O(n)$ Exact Deterministic Time & Space
Chazelle & Edelsbrunner 1992 $O( n \log n + k )$ $O(n+k)$ total? Exact Deterministic Time & Space
CHAZELLE 1986 $O( n*log^{2}(n)/(log log n) + k)$ $O(n+k)$ total (and possibly auxiliary as well?) Exact Deterministic Time & Space
Goodrich 1989 $O(\log^{2}(n))$ $O(n+k)$ total? Exact Parallel Time

Time Complexity Graph

Line segment intersection - Reporting all intersection points, line segments - Time.png

References/Citation

https://dl.acm.org/doi/10.1145/147508.147511

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

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Reporting_all_intersection_points,_line_segments&oldid=47651"