About this document
Szemerédi-Trotter Theorem Extensions by michael scott is a document available to read on EtoBox.
The document discusses bounds on incidences between point sets and curve sets in R^2. It summarizes the Szemerédi-Trotter theorem, which bounds the number of incidences between m points and n lines in R^2 by O(m^{2/3}n^{2/3}+m+n). It also discusses the Pach-Sharir theorem, which generalizes this to bound incidences between points and algebraic curves of constant degree. The document then proves a theorem bounding the sizes of two sets constructed from a point set A using polynomials, showing max(|A+A|,|f(A)
- Author
- michael scott
- Language
- EN