either , or that . In either case , giving the desired bound Proof of the second formulation Since every pair of points can be connected by at most one line, there can be at most lines which can connect at or more points, since . This bound will prove the theorem when is small (e.g. if for some absolute constant ). Thus, we need only consider the case when is large, say . Suppose that there are m lines that each contain at least points. These lines generate at least incidences, and so by the first formulation of the Szemerédi–Trotter theorem, we have and so at least one of the statements , or is true. The third possibility is ruled out since was assumed to be large, so we are left with the first two. But in either of these two cases, some elementary algebra will give the bound as desired. Optimality Except for its constant, the Szemerédi–Trotter incidence bound cannot be improved. To see this, consider for any positive integer a set of points on the integer lattice and a set of lines Clearly, and . Since each line is incident to points (i.e., once for each ), the number of incidences is which matches the upper bound. Generalization to One generalization of this result to arbitrary dimension, , was found by Agarwal and Aronov. Given a set of points, , and the set of hyperplanes, , which are each spanned by , the number of incidences between and is bounded above by Equivalently, the number of hyperplanes in containing or more points is bounded above by A construction due to Edelsbrunner shows this bound to be asymptotically optimal. József Solymosi and Terence Tao obtained near sharp upper bounds for the number of incidences between points and algebraic varieties in higher dimensions, when the points and varieties satisfy "certain pseudo-line type axioms". Their proof uses the Polynomial Ham Sandwich Theorem. In Many proofs of the Szemerédi–Trotter theorem over rely in a crucial way on the topology of Euclidean space, so do not extend easily to other fields. e.g. the original proof of Szemerédi and Trotter; the polynomial partitioning proof and the crossing number proof do not extend to the complex plane. Tóth successfully generalized the original proof of Szemerédi and Trotter to the complex plane by introducing additional ideas. This result was also obtained independently and through a