Unit Distances in Three Dimensions

DOI10.1017/S0963548312000144zbMath1250.52010arXiv1107.1077OpenAlexW2009553385MaRDI QIDQ2908130

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

Publication date: 4 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

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

zbMATH Keywords

number of unit distancespolynomial partitioning technique

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Cites Work

• Unnamed Item
• Refined bounds on the number of connected components of sign conditions on a variety
• VC dimensions of principal component analysis
• Combinatorial complexity bounds for arrangements of curves and spheres
• Algebraic methods in discrete analogs of the Kakeya problem
• On lines, joints, and incidences in three dimensions
• Generalized sandwich theorems
• Zur Zerlegung von Punktmengen in solche kleineren Durchmessers
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Using Algebraic Geometry
• On the number of cells defined by a family of polynomials on a variety
• On Sets of Distances of n Points
• Algorithms in real algebraic geometry

Related Items (19)

A semi-algebraic version of Zarankiewicz's problem ⋮ Sphere tangencies, line incidences and Lie’s line-sphere correspondence ⋮ Uniform distribution and geometric incidence theory ⋮ Concentration estimates for algebraic intersections ⋮ Refined bounds on the number of connected components of sign conditions on a variety ⋮ Polynomial partitioning for a set of varieties ⋮ Improved Bounds for Incidences Between Points and Circles ⋮ Distinct distances between points and lines ⋮ The polynomial method over varieties ⋮ On the number of discrete chains ⋮ Incidences between points and lines in \({\mathbb {R}}^4\) ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ 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 ⋮ Breaking the 3/2 Barrier for Unit Distances in Three Dimensions ⋮ Assorted musings on dimension-critical graphs ⋮ A Szemerédi-Trotter type theorem in \(\mathbb R^4\) ⋮ Multilevel polynomial partitions and simplified range searching

This page was built for publication: Unit Distances in Three Dimensions