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

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

2011-02-26

arxiv.org/abs/1102.5391v1

Mathematics

Combinatorics

Scientific paper

Recently Guth and Katz \cite{GK2} invented, as a step in their nearly complete solution of Erd\H{o}s's distinct distances problem, a new method for partitioning finite point sets in $\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\'edi--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.

Affiliated with

Also associated with

No associations

Rating

Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-302236