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

DOI10.1007/S00454-012-9443-3zbMath1259.52008arXiv1102.5391OpenAlexW2070280977MaRDI QIDQ714991

Haim Kaplan, Micha Sharir, Ji{ří} Matoušek

Publication date: 15 October 2012

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

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

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)

Related Items (27)

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

Cites Work

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

This page was built for publication: Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique