Difference between revisions of "Line Intersections"
Jump to navigation
Jump to search
Yashsherry (talk | contribs) (Created page with "== Problem Description== the line segment intersection problem supplies a list of line segments in the Euclidean plane and asks whether any two of them intersect (cross). ==...") |
Yashsherry (talk | contribs) |
||
| Line 4: | Line 4: | ||
== Bounds Chart == | == Bounds Chart == | ||
[[File:Line_segment_intersectionBoundsChart.png| | [[File:Line_segment_intersectionBoundsChart.png|1050px]] | ||
== Step Chart == | == Step Chart == | ||
Revision as of 11:33, 15 September 2021
Problem Description
the line segment intersection problem supplies a list of line segments in the
Euclidean plane and asks whether any two of them intersect (cross).
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | ||
| nlogn | ||
| Linear | ||
| logn |