The Open Problems Project

Next: Problem 40: The Number of Pointed Pseudotriangulations

Previous: Problem 38: Compatible Triangulations

Problem 39: Distances among Point Sets in \R^2 and \R^3

Statement

For a point set P in \R^d, let f_d(P) be the number of unit-distance point pairs: f_d(P) = \left| \{ (u,v) \mid u, v \in P , \, \|u-v\| = 1 \} \right| \; ; and let f_d(n) be the maximum over all sets of n points: f_d(n) = \max_{|P| = 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| \{ \|u-v\| \mid u, v \in P \} \right| \; ; and let g_d(n) be the minimum over all sets of n points: g_d(n) = \min_{|P|=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_2(n) = O(n^{4/3})~ [Szé97], [CEG+90], [SST84], and f_2(n) = \Omega(n^{1+c/\log\log n}) [Erd46]. f_3(n) = O(n^{5/3}) and f_3(n) = \Omega(n^{4/3} \log \log n) [Erd60]. For g_2(n), the best result is that g_2(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_2(n) < c n^{1+\epsilon} for some c>0 and for each \epsilon>0, and $500 to settle whether g_2(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.