TOPICS
Search

Szemerédi-Trotter Theorem

The Szemerédi-Trotter theorem bounds the number of incident pairs between n distinct points and m distinct straight lines in the real plane by

I(P,L)=O(n^(2/3)m^(2/3)+n+m),

with an absolute implied constant (Szemerédi and Trotter 1983). Here the counted pairs are (p,l) in P×L with p in l, and O denotes asymptotic notation.

Consequently, the number of lines containing at least k points of an n-point set is O(n^2/k^3+n/k) for k>=2. When k<=sqrt(n), this reduces to O(n^2/k^3), the formulation recorded as problem 1069. The additive terms in the full bounds are necessary when the two parameters have very different sizes.

This is problem 1069 in the Erdős problems collection (Bloom 2026).

See also

Erdős Problems, Incidence Geometry

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 1069." Accessed Oct. 26, 2026. https://www.erdosproblems.com/1069.Szemerédi, E. and Trotter, W. T., Jr. "Extremal Problems in Discrete Geometry." Combinatorica 3, 381-392, 1983. https://doi.org/10.1007/BF02579194.

Cite this as:

Weisstein, Eric W. "Szemerédi-Trotter Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Szemeredi-TrotterTheorem.html

Subject classifications