Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique

DOI10.1007/S00454-012-9443-3zbMATH Open1259.52008arXiv1102.5391OpenAlexW2070280977MaRDI QIDQ714991FDOQ714991

Authors: Haim Kaplan, Micha Sharir, Jiří Matoušek 

Publication date: 15 October 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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 $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.

Full work available at URL: https://arxiv.org/abs/1102.5391

Recommendations

• Incidences between points and lines in three dimensions
• Polynomial methods and incidence theory
• Incidences between points and lines in three dimensions
• Incidence theorems and their applications
• Improved bounds for incidences between points and circles

zbMATH Keywords

crossing numberalgebraic methodsincidencespartitioning polynomialpolynomial ham-sandwichspanning tree with low crossing number

Mathematics Subject Classification ID

Partitions of sets (05A18) Erd?s problems and related topics of discrete geometry (52C10) Linear incidence geometry (51A99)

Cites Work

• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Title not available (Why is that?)
• Efficient partition trees
• Title not available (Why is that?)
• On the Erdős distinct distances problem in the plane
• On the Betti Numbers of Real Varieties
• The measure of the critical values of differentiable maps
• Algorithms in real algebraic geometry
• 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
• Repeated angles in the plane and related problems
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On the Number of Incidences Between Points and Curves
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Range Searching with Semialgebraic Sets. II
• On a problem of K. Zarankiewicz
• On Sets of Distances of n Points
• Extremal problems in discrete geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• Algebraic methods in discrete analogs of the Kakeya problem
• Lower Bounds for Approximation by Nonlinear Manifolds
• A Szemerédi-Trotter type theorem in \(\mathbb R^4\)
• On an application of Guth-Katz theorem
• An incidence theorem in higher dimensions
• Cutting circles into pseudo-segments and improved bounds for incidences
• Title not available (Why is that?)
• Discrepancy and approximations for bounded VC-dimension
• Optimal partition trees
• Generalized sandwich theorems
• Unit distances in three dimensions
• An improved bound on the number of point-surface incidences in three dimensions
• On range searching with semialgebraic sets
• Quasi-optimal range searching in spaces of finite VC-dimension
• Incidences in Three Dimensions and Distinct Distances in the Plane
• Title not available (Why is that?)
• Spanning trees crossing few barriers
• VC dimensions of principal component analysis
• Title not available (Why is that?)
• Improved upper bounds for approximation by zonotopes

Cited In (28)

• Incidences with curves in \(\mathbb{R}^d\)
• Multilevel polynomial partitions and simplified range searching
• Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
• Improved restriction estimate for hyperbolic surfaces in \(\mathbb{R}^3\)
• New bounds for the same-type lemma
• Minimum-link paths revisited
• On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves
• Improved Bounds for Incidences Between Points and Circles
• The polynomial method over varieties
• On the Erdős distinct distances problem in the plane
• On the number of rich lines in high dimensional real vector spaces
• Polynomial partitioning for a set of varieties
• Improved bounds for the expected number of \(k\)-sets
• Ruled Surface Theory and Incidence Geometry
• Planar point sets determine many pairwise crossing segments
• Distinct Distances on Algebraic Curves in the Plane
• An incidence theorem in higher dimensions
• Distinct distances between points and lines
• Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
• On a real analog of Bézout inequality and the number of connected components of sign conditions
• A semi-algebraic version of Zarankiewicz's problem
• Few distinct distances implies no heavy lines or circles
• Distinct distance estimates and low degree polynomial partitioning
• A restriction estimate using polynomial partitioning
• Incidences between points and lines in \({\mathbb {R}}^4\)
• Computing the Distance between Piecewise-Linear Bivariate Functions
• Few cuts meet many point sets
• A note on the distinct distances problem in the hyperbolic plane

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)