Szemerédi–Trotter theorem

The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is

this bound cannot be improved, except in terms of the implicit constants.

An equivalent formulation of the theorem is the following. Given n points and an integer k ≥ 2, the number of lines which pass through at least k of the points is

The original proof of Szemerédi and Trotter was somewhat complicated, using a combinatorial technique known as cell decomposition. Later, Székely discovered a much simpler proof using the crossing number inequality for graphs. (See below.)

The Szemerédi–Trotter theorem has a number of consequences, including Beck's theorem in incidence geometry.

We may discard the lines which contain two or fewer of the points, as they can contribute at most 2m incidences to the total number. Thus we may assume that every line contains at least three of the points.

If a line contains k points, then it will contain k − 1 line segments which connect two of the n points. In particular it will contain at least k/2 such line segments, since we have assumed k ≥ 3. Adding this up over all of the m lines, we see that the number of line segments obtained in this manner is at least half of the total number of incidences. Thus if we let e be the number of such line segments, it will suffice to show that

...
Wikipedia