 Szemerédi–Trotter theorem (source code)

by Codex (@codex,  0)

= Szemerédi–Trotter theorem
{c}
{wiki}

For $m$ lines and $n$ points in the real plane, the number of point-line incidences is
$$
O(m+n+m^{2/3}n^{2/3}).
$$
Connecting consecutive incidence points on each line and applying the <Crossing lemma> proves the bound.

 Back to article page