Planar Graphs · Number of Crossings
Lesson 7
Theorem (Szemerédi — Trotter). For \(n\) points and \(m\) lines in the plane, the maximum number of incidences is \[\Theta\left(n^{\frac{2}{3}}m^{\frac{2}{3}}+n+m\right) \ .\]For the curious 🤓
From the just-proven theorem, one can derive the following result in combinatorial geometry.