For lines and points in the real plane, the number of point-line incidences isConnecting consecutive incidence points on each line and applying the Crossing lemma proves the bound.
For distinct points in the real plane, counts lines containing at least points. The Szemerédi–Trotter theorem applied to these lines gives the bound by absorbing its additive line-count term; bounded follows by counting point pairs. Consequently, summing occupancies of lines with at least points by dyadic ranges gives .
For distinct equal-radius circles and a finite point set in the real plane, incidences between points and curves satisfy . Scaling the plane reduces any common positive radius to one. The constant is universal. The fixed-radius condition bounds the number of circles through two prescribed distinct points by two.
For distinct real univariate polynomials of degree at most and points with distinct first coordinates, the number of incidences between the points and the polynomial graphs isTwo polynomial graphs meet at most times, so the graph formed from consecutive incidences has crossings; the Crossing lemma supplies the lower bound.
Articles by others on the same topic
The Szemerédi–Trotter theorem is a fundamental result in combinatorial geometry that provides bounds on the incidences between points and lines in the plane. Specifically, it addresses how many points lie on a set of lines, providing a relationship between three parameters: the number of points, the number of lines, and the number of incidences (that is, points that lie on those lines).