Szemerédi–Trotter-tétel

A Szemerédi–Trotter-tétel a matematika, ezen belül a diszkrét geometria egyik fontos tétele.

A tétel állítása

Ha a síkban adott n pont és m egyenes, akkor a köztük levő illeszkedések száma $O(n^{2/3}m^{2/3}+n+m)$.

A tétel másik formája

Ha a síkban adott n pont és k>2, akkor azon egyenesek száma, amelyek a pontok közül legalább k-t tartalmaznak $O(n^{2}/k^{3}+n/k)$.