Szemerédi-Trotter theorem

The number of incidences of a set of n points and a set of m lines in the real plane 2 is


Proof. Let’s consider the points as vertices of a graph, and connect two vertices by an edge if they are adjacent on some line. Then the number of edges is e=I-m. If e<4n then we are done. If e4n then by crossing lemma


and the theorem follows.

Recently, Tóth[1] extended the theorem to the complex planeMathworldPlanetmath 2. The proof is difficult.


  • 1 Csaba D. Tóth. The Szemerédi-Trotter theorem in the complex plane., May 2003.
Title Szemerédi-Trotter theorem
Canonical name SzemerediTrotterTheorem
Date of creation 2013-03-22 13:21:30
Last modified on 2013-03-22 13:21:30
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 7
Author bbukh (348)
Entry type Theorem
Classification msc 51A20
Classification msc 05C10