point-line incidences · 1983
↑ geometry pack · erdős · guthkatz · hadwiger · runner · kakeya · capset · heilbronn · borsuk · viazovska
m points + n lines in the plane share at most I = O((mn)2/3 + m + n) incidences. Erdős's construction makes the bound tight: a small thin grid of points and lines saturates it up to a constant. Swap modes to compare the tight construction against random placements.
As K grows, the Erdős construction's incidence count tracks (mn)2/3 exactly — a straight line of slope 2/3 in log-log space. Random placements never come close.
An incidence is a point lying on a line. Given m points and n lines in the Euclidean plane, how many incidences can there be? Each line can hit all m points only if all the points are collinear — and they aren't, in general — so the question is how the count grows with m and n.
I(P, L) ≤ C · (m · n)2/3 + m + n.
That's the Szemerédi–Trotter theorem. The constant C is harmless; what matters is the exponent. Naive upper bounds (every pair of points defines at most one line; every line is determined by two points) give Θ(m√n + n) or Θ(n√m + m), both worse than ST except in degenerate ranges. ST is the truth.
The exponent comes from a cell-decomposition argument due to Clarkson, Edelsbrunner, Guibas, Sharir, and Welzl: cut the plane into r² cells using r random lines, then count incidences inside cells (each cell has few points and few lines, by random sampling bounds) and across cells (each line crosses at most r cells). Optimising r drops out (mn)2/3.
A second proof — Kaplan, Matoušek, Sharir (2010), independently Guth (2014) — uses the polynomial method. A degree-d polynomial vanishing on the points forces lines with d+1 incidences to lie inside its zero set; Bézout-like bounds finish the count. The technique is exactly the one Dvir uses on kakeya and Guth–Katz use on guthkatz — the ST theorem is in many ways the seed crystal of the polynomial-method era.
Erdős had given a matching lower bound long before the theorem was proved. Take points on the integer grid {1,…,K} × {1,…,2K²}, and the lines y = ax + b with a ∈ {1,…,K}, b ∈ {1,…,K²}. Then:
Drag the K slider in the build tab to grow the construction. The
I / (mn)2/3 ratio is the constant 2−2/3 ≈ 0.63 —
flat in K. Random placements, by contrast, give I ≈ O(m + n) on expectation, far
below the bound.