next up previous
Next: Problem 40: The Number Up: The Open Problems Project Previous: Problem 38: Compatible Triangulations


Problem 39: Distances among Point Sets in $ \mathbb {R}$2 and $ \mathbb {R}$3

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

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

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

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

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

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

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

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

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

Origin
Paul Erdős [Erd46].
Status/Conjectures
Open.
Partial and Related Results
f2(n) = O(n4/3)  [Szé97,CEG+90,SST84], and f2(n) = Ω(n1+c/loglog n) [Erd46]. f3(n) = O(n5/3) and f3(n) = Ω(n4/3loglog n) [Erd60]. For g2(n), the best result is that g2(n) = Ω(n6/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 f2(n) < cn1+ε for some c > 0 and for each ε > 0, and $500 to settle whether g2(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.


next up previous
Next: Problem 40: The Number Up: The Open Problems Project Previous: Problem 38: Compatible Triangulations
The Open Problems Project - December 08, 2012