Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique (Q714991): Difference between revisions

The paper reproves some classical theorems of discrete geometry (the Szemerédi-Trotter theorem and the Pach-Sharir theorem bounding the number of incidences between points and lines, and the theorem of Chazelle and Welzl about spanning trees with low crossing number) using the Guth-Katz partitioning of finite point sets in a Euclidean space based on the Stone-Tukey ham-sandwich theorem. The proofs are self-contained and appropriate for teaching.