Problem 39: Distances among Point Sets in $\mathbb {R}$² and $\mathbb {R}$³

Statement

For a point set P in $\mathbb {R}$^d, let f_d(P) be the number of unit-distance point pairs:

f_d(P) = $$\left\vert\vphantom{ \{ (u,v) \mid u, v \in P , \Vert u-v\Vert = 1 \} }\right.$${(u, v) | u, v $$\in$$ P, | u - v| = 1}$$\left.\vphantom{ \{ (u,v) \mid u, v \in P , \Vert u-v\Vert = 1 \} }\right\vert$$  ;

and let f_d(n) be the maximum over all sets of n points:

f_d(n) = $$\max_{{\vert P\vert = n}}^{}$$f_d(P)  .

Further, let g_d(P) denote the number of distinct distances induced by a set of points P:

g_d(P) = $$\left\vert\vphantom{ \{ \Vert u-v\Vert \mid u, v \in P \} }\right.$${| u - v| | u, v $$\in$$ P}$$\left.\vphantom{ \{ \Vert u-v\Vert \mid u, v \in P \} }\right\vert$$  ;

and let g_d(n) be the minimum over all sets of n points:

g_d(n) = $$\min_{{\vert P\vert=n}}^{}$$g_d(P)  .

Give upper and lower bounds on f_d(n) and g_d(n), particularly for d = 2 and d = 3.

Origin

Paul Erdős [Erd46].

Status/Conjectures

Open.

Partial and Related Results

f₂(n) = O(n^4/3)  [Szé97,CEG+90,SST84], and f₂(n) = $\Omega$(n^{1+c/loglog n}) [Erd46]. f₃(n) = O(n^5/3) and f₃(n) = $\Omega$(n^4/3loglog n) [Erd60]. For g₂(n), the best result is that g₂(n) = $\Omega$(n^6/7) [ST01a]. Erdős conjectured that the correct answer here is n/$\sqrt{{\log n}}$; this bound is achieved on the grid.

Reward

Erdős offered $500 to settle whether f₂(n) < cn^1+$\epsilon$ for some c > 0 and for each $\epsilon$ > 0, and $500 to settle whether g₂(n) = [1 + o(1)]cn/$\sqrt{{\log n}}$.

Appearances

[CFG90, pp. 150-1].

Categories

combinatorial geometry

Entry Revision History

S. Venkatasubramanian, 12 Feb. 2002.

Bibliography

CEG+90

K. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Emo Welzl.
Combinatorial complexity bounds for arrangements of curves and spheres.
Discrete Comput. Geom., 5:99-160, 1990.

CFG90

H. P. Croft, K. J. Falconer, and R. K. Guy.
Unsolved Problems in Geometry.
Springer-Verlag, 1990.

Erd46

P. Erdős.
On sets of distances of n points.
Amer. Math. Monthly, 53:248-250, 1946.

Erd60

P. Erdős.
On sets of distances of n points in Euclidean space.
Publications Mathematical Institute of Hungarian Academy of Sciences, 5:165-169, 1960.

Szé97

L. A. Székely.
Crossing numbers and hard Erdős problems in discrete geometry.
Combinatorics, Probability and Computing, 6:353-358, 1997.

SST84

J. Spencer, E. Szemerédi, and W. T. Trotter.
Unit distances in the Euclidean plane.
In B. Bollobás, editor, Graph Theory and Combinatorics, pages 293-303. Academic Press, New York, NY, 1984.

ST01a

J. Solymosi and Cs. D. Tóth.
Distinct distances in the plane.
Discrete Comput. Geom., 25(4):629-634, 2001.