Near optimal bounds for the Erdős distinct distances problem in high dimensions
type: Item
instance of: scholarly article
title: Near optimal bounds for the Erdős distinct distances problem in high dimensions
zbMATH Open document ID: 1174.52009
author: József Solymosi
author: Van Vu
published in: Combinatorica
publication date: 2008-10-21T00:00:00Z
review text: One of Erdős' most famous questions in combinatorial geometry is to determine \(g_d(n)\), the minimum number of distinct distances that can occur between \(n\) points in \(\mathbb R^d\). An appropriately scaled integer lattice shows that \(g_d(n)=O(n^{2/d})\). It is conjectured that \(g_d(n)\) is not far from this bound when \(d\) is large. In this paper it is shown that \(g_3(n)=\Omega(n^{0.5643})\) and \(g_d(n)=\Omega(n^{\frac{2}{d}-\frac{2}{d(d+2)}})\) for all \(d\geq 4\). These bounds improve the previous records of \textit{B. Aronov, J. Pach, M. Sharir}, and \textit{G. Tardos} [Comb. Probab. Comput. 13, 283-293 (2004; Zbl 1052.52010)]. In fact, slightly better bounds are proven which follow from two recursive lower bounds that depend on the maximum number of points that lie on a hyperplane of codimension \(1\) and codimension \(2\), respectively. The proof is a clever counting argument based on a modification of the cutting lemma of \textit{B. Chazelle} and \textit{J. Friedman} [Combinatorica 10, 229-449 (1990; Zbl 0715.68036)].
reviewed by: Konrad J. Swanepoel
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 5355089
zbMATH Keywords: distinct distance problem
zbMATH Keywords: Erdős problem
zbMATH Keywords: cutting lemma
zbMATH Keywords: combinatorial geometry
MaRDI profile type: Publication
full work available at URL: s00493-008-2099-1
OpenAlex ID: W2031397195
cites work: Distinct Distances in Three and Higher Dimensions
cites work: A deterministic view of random sampling and its use in geometry
cites work: The number of different distances determined by n points in the plane
cites work: The number of different distances determined by a set of points in the Euclidean plane
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: On Sets of Distances of n Points
cites work: Curvature, combinatorics, and the Fourier transform
cites work: On the Different Distances Determined by n Points
cites work: Distinct distances in the plane
cites work: Q4657595
cites work: Crossing Numbers and Hard Erdős Problems in Discrete Geometry
cites work: On distinct sums and distinct distances.
DOI: 10.1007/S00493-008-2099-1
Recommended article: On the Erdős distinct distances problem in the plane
Recommended article: A New Lower Bound for the Distinct Distance Constant
Recommended article: A new bound for the Erdős distinct distances problem in the plane over prime fields
Recommended article: Erdös distance problems in normed spaces
Recommended article: A reduction for the distinct distances problem in \(\mathbb{R}^d\)
Recommended article: Distinct distance estimates and low degree polynomial partitioning
Recommended article: Q4657595
Recommended article: New Bounds for Approximating Extremal Distances in Undirected Graphs
Recommended article: Q4657584
description: scientific article; zbMATH DE number 5355089