Reporting all intersection points, line segments: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision 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})$ || | | [[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)$ | | [[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( | | [[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]] | ||
== 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
