Line Intersections
Problem Description
Lines that are non-coincident and non-parallel 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) Jean-Daniel Boissonnat and Franco P. Preparata. (1997) [An optimal algorithm for finding segment intersections. (1995)] |
|
| Linear | ||
| logn | Goodrich; 1989 (1989) |