Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique

Abstract

Recently Guth and Katz \cite{GK2} invented, as a step in their nearly complete solution of Erdős's distinct distances problem, a new method for partitioning finite point sets in ${\mathbb{R}}^d$, based on the Stone--Tukey polynomial ham-sandwich theorem. We apply this method to obtain new and simple proofs of two well known results: the Szemerédi--Trotter theorem on incidences of points and lines, and the existence of spanning trees with low crossing numbers. Since we consider these proofs particularly suitable for teaching, we aim at self-contained, expository treatment. We also mention some generalizations and extensions, such as the Pach--Sharir bound on the number of incidences with algebraic curves of bounded degree.

References in corpus (1)

• On the Erdos distinct distance problem in the plane

Cited by in corpus (9)

• On a theorem of Schoen and Shkredov on sumsets of convex sets
• Counting joints with multiplicities
• Incidences between points and lines in R^4
• On the number of classes of triangles determined by $N$ points in ${\mathbb{R}}^2$
• An incidence theorem in higher dimensions
• Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory
• Distinct and repeated distances on a surface and incidences between points and spheres
• Highly incidental patterns on a quadratic hypersurface in ${\mathbb{R}}^4$
• Incidences with curves in R^d