Szemerédi–Trotter-tétel

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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).