Difference between revisions of "Line Intersections"
Yashsherry (talk  contribs) 
Yashsherry (talk  contribs) 

Line 1:  Line 1:  
== Problem Description==  == Problem Description==  
the  Lines that are noncoincident and nonparallel intersect at a unique point. Lines are said to intersect each other if they cut each other at a point. By Euclid's lemma two lines can have at most 11 point of intersection.  
To find the intersection of two lines, you first need the equation for each line. At the intersection, xx and yy have the same value for each equation. This means that the equations are equal to each other. We can therefore solve for xx. Substitute the value of xx in one of the equations (it does not matter which) and solve for yy.  
== Bounds Chart ==  == Bounds Chart == 
Latest revision as of 13:42, 15 September 2021
Problem Description
Lines that are noncoincident and nonparallel intersect at a unique point. Lines are said to intersect each other if they cut each other at a point. By Euclid's lemma two lines can have at most 11 point of intersection.
To find the intersection of two lines, you first need the equation for each line. At the intersection, xx and yy have the same value for each equation. This means that the equations are equal to each other. We can therefore solve for xx. Substitute the value of xx in one of the equations (it does not matter which) and solve for yy.
Bounds Chart
Step Chart
Improvement Table
Complexity Classes  Algorithm Paper Links  Lower Bounds Paper Links 

Exp/Factorial  
Polynomial > 3  
Cubic  
Quadratic  [ Naive (1940)]  
nlogn  Bentley–Ottmann algorithm (1979)
Chazelle & Edelsbrunner (1992) (1992) NIEVERGELT. J.. AND PREPARATA 1982 (1982) JeanDaniel Boissonnat and Franco P. Preparata. (1997) [An optimal algorithm for finding segment intersections. (1995)] 

Linear  
logn  Goodrich; 1989 (1989) 