# Line Intersections

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

## 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.

## Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic [- Naive (1940)]
nlogn Bentley–Ottmann algorithm (1979)

[An optimal algorithm for finding segment intersections. (1995)]

Linear
logn Goodrich; 1989 (1989)