Difference between revisions of "Line Intersections"

From Algorithm Wiki
Jump to navigation Jump to search
(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). ==...")
 
Line 4: Line 4:


== Bounds Chart ==
== Bounds Chart ==
[[File:Line_segment_intersectionBoundsChart.png|350px]]
[[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

Line segment intersectionBoundsChart.png

Step Chart

Line segment intersectionStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn