Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
From MaRDI portal
Publication:714991
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
crossing numberalgebraic methodsincidencespartitioning polynomialpolynomial ham-sandwichspanning tree with low crossing number
Partitions of sets (05A18) Erd?s problems and related topics of discrete geometry (52C10) Linear incidence geometry (51A99)
Related Items
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
