Reporting all intersection points, line segments (Line segment intersection)
Jump to navigation
Jump to search
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(n+k)$ total ($O({1})$ auxiliary if excluding input and output) | Exact | Deterministic | |
| Bentley–Ottmann algorithm | 1979 | $O( n log n + k log n)$ | $O(n)$ auxiliary | Exact | Deterministic | Time & Space |
| Chazelle & Edelsbrunner | 1992 | $O( nlog 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
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Time-Space Tradeoff
Error creating thumbnail: Unable to save thumbnail to destination
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)