Unit distances in three dimensions
From MaRDI portal
Abstract: We show that the number of unit distances determined by n points in R^3 is O(n^{3/2}), slightly improving the bound of Clarkson et al. established in 1990. The new proof uses the recently introduced polynomial partitioning technique of Guth and Katz [arXiv:1011.4105]. While this paper was still in a draft stage, a similar proof of our main result was posted to the arXiv by Joshua Zahl [arXiv:1104.4987].
Recommendations
Cites work
- Algebraic methods in discrete analogs of the Kakeya problem
- Algorithms in real algebraic geometry
- Combinatorial complexity bounds for arrangements of curves and spheres
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Generalized sandwich theorems
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- On lines, joints, and incidences in three dimensions
- On Sets of Distances of n Points
- On the number of cells defined by a family of polynomials on a variety
- Refined bounds on the number of connected components of sign conditions on a variety
- Using Algebraic Geometry
- VC dimensions of principal component analysis
- Zur Zerlegung von Punktmengen in solche kleineren Durchmessers
Cited in
(25)- Distinct distances between points and lines
- Three distinct distances in the plane
- The polynomial method over varieties
- Multilevel polynomial partitions and simplified range searching
- A semi-algebraic version of Zarankiewicz's problem
- Uniform distribution and geometric incidence theory
- On a real analog of Bézout inequality and the number of connected components of sign conditions
- Refined bounds on the number of connected components of sign conditions on a variety
- Sphere tangencies, line incidences and Lie's line-sphere correspondence
- On the number of discrete chains
- scientific article; zbMATH DE number 3893918 (Why is no real title available?)
- Breaking the 3/2 Barrier for Unit Distances in Three Dimensions
- Incidences between points and lines in \({\mathbb {R}}^4\)
- Polynomial partitioning for a set of varieties
- Improved bounds for incidences between points and circles
- Erratum: “Breaking the 3/2 barrier for unit distances in three dimensions”
- Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
- Concentration estimates for algebraic intersections
- Assorted musings on dimension-critical graphs
- Maximum Betti numbers of Čech complexes
- Almost sharp bounds on the number of discrete chains in the plane
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- Incidences with curves in \(\mathbb{R}^d\)
- Maximum Betti numbers of Čech complexes
- A Szemerédi-Trotter type theorem in R^4
This page was built for publication: Unit distances in three dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908130)
