Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
From MaRDI portal
Publication:714991
Abstract: Recently Guth and Katz cite{GK2} invented, as a step in their nearly complete solution of ErdH{o}s's distinct distances problem, a new method for partitioning finite point sets in , 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5999585 (Why is no real title available?)
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 1749054 (Why is no real title available?)
- scientific article; zbMATH DE number 2145241 (Why is no real title available?)
- scientific article; zbMATH DE number 3210572 (Why is no real title available?)
- scientific article; zbMATH DE number 3053541 (Why is no real title available?)
- scientific article; zbMATH DE number 3065505 (Why is no real title available?)
- A Szemerédi-Trotter type theorem in \(\mathbb R^4\)
- Algebraic methods in discrete analogs of the Kakeya problem
- Algorithms in real algebraic geometry
- An improved bound on the number of point-surface incidences in three dimensions
- An incidence theorem in higher dimensions
- Combinatorial complexity bounds for arrangements of curves and spheres
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Cutting circles into pseudo-segments and improved bounds for incidences
- Discrepancy and approximations for bounded VC-dimension
- Efficient partition trees
- Extremal problems in discrete geometry
- Generalized sandwich theorems
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Improved upper bounds for approximation by zonotopes
- Incidences in three dimensions and distinct distances in the plane
- Lower Bounds for Approximation by Nonlinear Manifolds
- On Sets of Distances of n Points
- On a problem of K. Zarankiewicz
- On an application of Guth-Katz theorem
- On range searching with semialgebraic sets
- On range searching with semialgebraic sets. II.
- On the Betti Numbers of Real Varieties
- On the Erdős distinct distances problem in the plane
- On the Number of Incidences Between Points and Curves
- Optimal partition trees
- Quasi-optimal range searching in spaces of finite VC-dimension
- Repeated angles in the plane and related problems
- Spanning trees crossing few barriers
- The measure of the critical values of differentiable maps
- Unit distances in three dimensions
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- VC dimensions of principal component analysis
Cited in
(28)- Distinct distance estimates and low degree polynomial partitioning
- Polynomial partitioning for a set of varieties
- Incidences between points and lines in \({\mathbb {R}}^4\)
- Improved bounds for incidences between points and circles
- Incidences with curves in \(\mathbb{R}^d\)
- Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
- Ruled surface theory and incidence geometry
- Distinct Distances on Algebraic Curves in the Plane
- Multilevel polynomial partitions and simplified range searching
- Improved bounds for the expected number of \(k\)-sets
- On an application of Guth-Katz theorem
- On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves
- Polynomial methods and incidence theory
- Few cuts meet many point sets
- The polynomial method over varieties
- On the number of rich lines in high dimensional real vector spaces
- A semi-algebraic version of Zarankiewicz's problem
- Few distinct distances implies no heavy lines or circles
- An incidence theorem in higher dimensions
- On the Erdős distinct distances problem in the plane
- Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
- On a real analog of Bézout inequality and the number of connected components of sign conditions
- A restriction estimate using polynomial partitioning
- Distinct distances between points and lines
- New bounds for the same-type lemma
- Minimum-link paths revisited
- A note on the distinct distances problem in the hyperbolic plane
- Improved restriction estimate for hyperbolic surfaces in \(\mathbb{R}^3\)
This page was built for publication: Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714991)
