Line Intersections

From Algorithm Wiki
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.

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 [- Naive (1940)]
nlogn Bentley–Ottmann algorithm (1979)

Chazelle & Edelsbrunner (1992) (1992)

CHAZELLE 1986 (1986)

NIEVERGELT. J.. AND PREPARATA 1982 (1982)

Jean-Daniel Boissonnat and Franco P. Preparata. (1997)

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

Boissonnat; Snoeyink 1999 (1999)

Linear
logn Goodrich; 1989 (1989)